Cycles passing through k + 1 vertices in k‐connected graphs

In this article, we prove the following theorem. Let k ≥ 3 be an integer, G be a k‐connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min {2d,|V(G)|} passing through X. This result gives the positive answer to the Question posed by Locke [8]. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:179–190, 2008     

A list version of Dirac's theorem on the number of edges in colour‐critical graphs

One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 ( 4 ) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension of this result, Dirac [G. A. Dirac, Proc London Math Soc 7(3) ( 7 ) 161–195] proved that every k‐colour‐critical graph (k ≥ 4) on n ≥ k + 2 vertices has at least ½((k ? 1) n + k ? 3) edges. The aim of this paper is to prove a list version of Dirac's result and to extend it to hypergraphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 165–177, 2002; DOI 10.1002/jgt.998     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

An excluded minor theorem for the Octahedron plus an edge

Let G be the unique 4‐connected simple graph obtained by adding an edge to the Octahedron. Every 4‐connected graph that does not contain a minor isomorphic to G is either planar or the square of an odd cycle. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 124–130, 2008     

On the Thomassen's conjecture*

C. Thomassen proposed a conjecture: Let G be a k‐connected graph with the stability number α ≥ k, then G has a cycle C containing k independent vertices and all their neighbors. In this paper, we will obtain the following result: Let G be a k‐connected graph with stability number α = k + 3 and C any longest cycle of G, then C contains k independent vertices and all their neighbors. This solves Thomassen's conjecture for the case α = k + 3. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 168–180, 2001     

A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

Cycles of even lengths modulo k

Thomassen [J Graph Theory 7 (1983), 261–271] conjectured that for all positive integers k and m, every graph of minimum degree at least k+1 contains a cycle of length congruent to 2m modulo k. We prove that this is true for k?2 if the minimum degree is at least 2k?1, which improves the previously known bound of 3k?2. We also show that Thomassen's conjecture is true for m = 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 246–252, 2010     

Nearly light cycles in embedded graphs and crossing‐critical graphs

We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large k‐crossing‐critical graph has crossing number at most 2k + 23. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 151–156, 2006     

Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000     

Short proofs for two theorems of Chien,Hell and Zhu

In (J Graph Theory 33 (2000), 14–24), Hell and Zhu proved that if a series–parallel graph G has girth at least 2?(3k?1)/2?, then χ_c(G)≤4k/(2k?1). In (J Graph Theory 33 (2000), 185–198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14–24) is sharp. Short proofs of both results are given in this note. © 2010 Wiley Periodicals, Inc. J Graph 66: 83‐88, 2010 Theory     

Snarks with given real flow numbers

We show that for each rational number r such that 4<r?5 there exist infinitely many cyclically 4‐edge‐connected cubic graphs of chromatic index 4 and girth at least 5—that is, snarks—whose flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circular flow numbers, J Graph Theory 43 [2003], 304–318]. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 189‐201, 2011     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

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     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Minor‐order obstructions for the graphs of vertex cover 6

We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to k–VERTEX COVER graph families. In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of vertices for connected (disconnected) obstructions are shown to be sharp for all k > 0. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 163–178, 2002     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Tree‐width and circumference of graphs

We prove that every graph of circumference k has tree‐width at most k ? 1 and that this bound is best possible. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 24–25, 2003     

Bounds related to domination in graphs with minimum degree two

A dominating set for a graph G = (V,E) is a subset of vertices V′ ⊆ V such that for all v E V − V′ there exists some u E V′ for which {v, u} E E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q edges, the domination number is bounded by (q + 1)/3. From this we derive exact lower bounds for the number of edges of a connected graph with minimum degree at least 2 and a given domination number. We also generalize the bound to k-restricted domination numbers; these measure how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be incluced in the dominating set. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 139–152, 1997     

Girth of sparse graphs

For each fixed k ≥ 0, we give an upper bound for the girth of a graph of order n and size n + k. This bound is likely to be essentially best possible as n → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.