Minimum vertex‐diameter‐2‐critical graphs

We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on n ≥ 23 vertices is (5n ? 17)/2 if n is odd, and is (5n/2) ? 7 if n is even. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Multipartite Ramsey numbers for odd cycles

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K((n?1)/2, (n?1)/2, (n?1)/2, (n?1)/2, 1) there is a monochromatic C_n, a cycle of length n. This roughly says that the Ramsey number for C_n (i.e. 2n?1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K_2n?1 the edges within a set of size (n+ 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009     

A lower bound on the order of regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 ( 1 ), 209–218]. A (δ, g)‐cage is a smallest δ‐regular graph with girth g. For all δ ≥ 3 and odd girth g ≥ 5, Harary and Kovács conjectured the existence of a (δ,g)‐cage that contains a cycle of length g + 1. In the main theorem of this article we present a lower bound on the order of a δ‐regular graph with odd girth g ≥ 5 and even girth h ≥ g + 3. We use this bound to show that every (δ,g)‐cage with δ ≥ 3 and g ∈ {5,7} contains a cycle of length g + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g. Moreover, for every odd g ≥ 5, we prove that the even girth of all (δ,g)‐cages with δ large enough is at most (3g ? 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

The chromatic Ramsey number of odd wheels

We prove that the chromatic Ramsey number of every odd wheel W_{2k+ 1}, k?2 is 14. That is, for every odd wheel W_{2k+ 1}, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W_{2k+ 1} in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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     

Small odd cycles in 4‐chromatic graphs*

It is shown that every 4‐chromatic graph on n vertices contains an odd cycle of length less than . This improves the previous bound given by Nilli [J Graph Theory 3 ( 3 ), 145–147]. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 115–117, 2001     

Large components in r‐edge‐colorings of Kn have diameter at most five

Reflecting on problems posed by Gyárfás [Ramsey Theory Yesterday, Today and Tomorrow, Birkhäuser, Basel, 2010, pp. 77–96] and Mubayi [Electron J Combin 9 (2002), #R42], we show in this note that every r‐edge‐coloring of K_n contains a monochromatic component of diameter at most five on at least n/(r?1) vertices. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 337–340, 2012     

Minimum C5‐saturated graphs

A graph is C₅‐saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. We prove that the minimum number of edges in a C₅ ‐saturated graph on n≥11 vertices is sat(n, C₅)=?10(n?1)/7??1 if n∈N₀={11, 12, 13, 14, 16, 18, 20} and is ?10(n?1)/7? if n≥11 and n?N₀. © 2009 Wiley Periodicals, Inc. J Graph Theory     

All minimum C5‐saturated graphs

A graph is C₅‐ saturated if it has no five‐cycle as a subgraph, but does contain a C₅ after the addition of any new edge. Extending our previous result, we prove that the minimum number of edges in a C₅‐saturated graph on n vertices is sat(n, C₅) = ?10(n ? 1)/7? ? 1 for 11≤n≤14, or n = 16, 18, 20, and is ?10(n ? 1)/7? for all other n≥5, and we also prove that the only C₅‐saturated graphs with sat(n, C₅) edges are the graphs described in Section 2 . © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 9‐26, 2011     

The existence of a 2‐factor in K1, n‐free graphs with large connectivity and large edge‐connectivity

In this article, we study the existence of a 2‐factor in a K_{1, n}‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K_{1, n}‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K_{1, n}‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K_{1, n}‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K_{1, n}‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K_{1, n}‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011     

Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvári proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Independence,odd girth,and average degree

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n?m?1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011     

On bipartite 2‐factorizations of kn − I and the Oberwolfach problem

It is shown that if F₁, F₂, …, F_t are bipartite 2‐regular graphs of order n and α₁, α₂, …, α_t are positive integers such that α₁ + α₂ + ? + α_t = (n ? 2)/2, α₁≥3 is odd, and α_i is even for i = 2, 3, …, t, then there exists a 2‐factorization of K_n ? I in which there are exactly α_i 2‐factors isomorphic to F_i for i = 1, 2, …, t. This result completes the solution of the Oberwolfach problem for bipartite 2‐factors. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:22‐37, 2011     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

An application of the combinatorial Nullstellensatz to a graph labelling problem

An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K₂, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=p^k vertices, where p is an odd prime and k is a positive integer that admits a C_p‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010.     

Short odd cycles in 4‐chromatic graphs

It is shown that any 4‐chromatic graph on n vertices contains an odd cycle of length smaller than √8n. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 145–147, 1999     

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory