Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9

A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤ w. Let be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w(H). It is proved that the cycle C_s is light if and only if 3 ≤ s ≤ 6, where w(C₃) = 21 and w(C₄) ≤ 35. The 4‐cycle with one diagonal is not light in , but it is light in the subclass consisting of all triangulations. The star K_1,s is light if and only if s ≤ 4. In particular, w(K_1,3) = 23. The paths P_s are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w(P₃) = 17 and w(P₄) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

Note on non-separating and removable cycles in highly connected graphs

We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense.     

Total colorings of planar graphs with maximum degree at least 8

Planar graphs with maximum degree Δ ⩾ 8 and without 5- or 6-cycles with chords are proved to be (δ + 1)-totally-colorable. This work was supported by Natural Science Foundation of Ministry of Education of Zhejiang Province, China (Grant No. 20070441)     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

直径为3的3-正则简单平面图的完全刻画

通过对子图和围长的研究,完全刻画了直径为3的3-正则简单平面图,获得了这类图仅有的11个非同构图.     

Infinite families of crossing‐critical graphs with prescribed average degree and crossing number

?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010     

Construction of a family of graphs with a small induced proper subgraph with minimum degree 3

We investigate the following question proposed by Erd?s: Is there a constant c such that, for each n, if G is a graph with n vertices, 2n-1edges, andδ(G)?3, then G contains an induced proper subgraph H with at least cn vertices andδ(H)?3?Previously we showed that there exists no such constant c by constructing a family of graphs whose induced proper subgraph with minimum degree 3 contains at most vertices. In this paper we present a construction of a family of graphs whose largest induced proper subgraph with minimum degree 3 is K₄. Also a similar construction of a graph with n vertices and αn+β edges is given.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Nested hierarchies in planar graphs

We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tree structure where neighboring bubbles are joined together by a 3-clique. Bubbles naturally provide the subdivision of G into communities and the tree structure defines the hierarchical relations between these communities.     

Note on 3-choosability of planar graphs with maximum degree 4

Deciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are such, most of the effort was focused to solving Havel’s and Steinberg’s conjectures. In this paper, we prove that every planar graph obtained as a subgraph of the medial graph of any bipartite plane graph is 3-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.     

A note on Z 3-connected graphs with degree sum condition

A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.     

On k‐ordered graphs

Ng and Schultz [J Graph Theory 1 ( 6 ), 45–57] introduced the idea of cycle orderability. For a positive integer k, a graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a Hamiltonian cycle, then G is said to be k‐ordered Hamiltonian. We give sum of degree conditions for nonadjacent vertices and neighborhood union conditions that imply a graph is k‐ordered Hamiltonian. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 69–82, 2000     

3-trees with few vertices of degree 3 in circuit graphs

A circuit graph(G,C) is a 2-connected plane graph G with an outer cycle C such that from each inner vertex v, there are three disjoint paths to C. In this paper, we shall show that a circuit graph with n vertices has a 3-tree (i.e., a spanning tree with maximum degree at most 3) with at most vertices of degree 3. Our estimation for the number of vertices of degree 3 is sharp. Using this result, we prove that a 3-connected graph with n vertices on a surface F_χ with Euler characteristic χ≥0 has a 3-tree with at most vertices of degree 3, where c_χ is a constant depending only on F_χ.     

A tight lower bound on the maximum genus of 3-edge connected loopless graphs

1.IntroductionThernchmumgenusl7M(G),ofacormectedgraphG~(V,E)isthem~amongthegenera,amongwhichGhasacellularembeddingonaspherewithkhandles.SinceanyembeddingofGhasatleastonefaCe,byEulerpolyhedralequation,itcanbeobtainedthatwhereP(G)=IE(G)I--IV(G)l IisthecyclerankofG.AgraphGiscalledop-imbeddableif7M(C)=Lop]exactly.Kund.[1]provedthatthereareatleasttWOedge-disjointspanningtreesinGifGis4-edgecormected.LiuandXuongcharacterizedtheuptheeddabilityofgraphsasinthefollowing.Theorem1.112'31.Acorm…