Chromatic number and minimum degree of K -free graphs r Vladimir Nikiforov Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152 0 1 email: [email protected] 0 2 January 13, 2010 n a J 3 Abstract 1 Let δ(G) bethe minimum degree of a graph G. Anumber of famous results abouttriangle- ] O free graphs determine the maximum chromatic number of graphs of order n with δ(G) > n/3. In this note these results are extended to K -free graphs of order n with δ(G) > C r+1 . (1−2/(2r−1)n. In particular: h (a) there exist K -free graphs of order n with δ(G) > (1−2/(2r−1))n − o(n) and t r+1 a arbitrary large chromatic number; m (b)if Gis aK -freegraphof ordern withδ(G) > (1−2/(2r−1))n,thenχ(G) ≤ r+2; r+1 [ (c) the structure of the (r+1)-chromatic K -free graphs of order n, with δ(G) > r+1 1 (1−2/(2r−1)n is found. v 0 Keywords: K -free graph; minimum degree; chromatic number; Andra´sfai graph; Hajnal r 7 graph. 0 2 . 1 1 Introduction and main results 0 0 1 In notation we follow [3]. In 1962 Andr´asfai [2] introduced the function : v i X ψ(n,r,h) = max{δ(G) : G is a K -free graph of order n with χ(G) ≥ h}, r+1 r a which has been widely studied during the years. One of the first contributions were the famous theorem and example of Andr´asfai, Erd˝os and S´os [1] showing that for every r ≥ 2, 3 3 1− n+O(1) ≤ ψ(n,r,r) ≤ 1− n. (1) (cid:18) 3r−1(cid:19) (cid:18) 3r −1(cid:19) Another milestone along this road is an example of Hajnal [9] showing that ψ(n,2,h) > n/3− o(n) for every h ≥ 3; for an updated version of Hajnal’s example see Example 8 below. Thus, for r = 2, this example leaves unanswered only one simple, yet tricky question: how large can be χ(G) of a K -free graph G of order n with δ(G) > n/3. 3 Erd˝os and Simonovits [9] conjectured that all K -free graphs of order n with δ(G) > n/3 are 3 3-chromatic, but this was disproved by H¨aggkvist [10], who described for every k ≥ 1 a 10k-regular, 1 4-chromatic, K -free graph of order 29k, for a description see Example 10 below. The example 3 of H¨aggkvist is based on the Mycielski graph M , also known as the Gro¨tzsch graph, which is a 3 4-chromatic K -free graph of order 11. We shall see later that M is a true landmark in this area, 3 3 but let us first recall the Mycielski graphs given in [15]: a sequence M ,M ,... of K -free graphs 1 2 3 with χ(M ) = i+1, constructed as follows: i Set M = K . To obtain M : write v ,...,v for the vertices of M ; choose n+1 other vertices 1 2 i+1 1 n i u ,...,u ; for every i ∈ [n] join u precisely to the neighbors of v ; join u to u ,...,u . 1 n+1 i i 2n+1 1 n Other graphs crucial in the study of ψ(n,r,h) are the K -free 3-chromatic Andr´asfai graphs 3 A ,A ,..., first described in [2]: 1 2 Set A = K and for every i ≥ 2 let A be the complement of the (i−1)’th power of C . 1 2 i 3i−1 In[11], Jinproved thefollowingtheorem, generalizing thecaser = 2ofthetheoremofAndr´asfai, Erd˝os and S´os and a result of H¨aggkvist from [10]. Theorem A Let 1 ≤ k ≤ 9, and let G be a K -free graph of order n. If 3 k +1 δ(G) > n, 3k +2 then G is homomorphic to A . k Note that this result is tight: taking the graph A , and blowing it up by a factor t, we obtain k+1 a K -free graph G of order n = (3k +2)t vertices, with δ(G) = (k +1)n/(3k +2), which is not 3 homomorphicto A .Notealso thatall graphssatisfying thepremises ofTheorem Aare3-chromatic. k Addressing thislastissue, Jin[12], andChen, JinandKoh[8]gaveafinercharacterizationofK -free 3 graphs with δ > n/3. Theorem B Let G be a K -free graph of order n, with δ(G) > n/3. If χ(G) ≥ 4, then 3 M ⊂ G. If χ(G) = 3 and 3 k +1 δ(G) > n, 3k +2 then G is homomorphic to A . k Later Brandt and Pisanski [4] found an infinite family of 4-chromatic, K -free graphs with 3 δ(G) > n/3. All these interesting results shed some light on the structure of dense K -free graphs, 3 but could not answer the original question of Erd˝os and Simonovits. The answer was given by Brandt and Thomass´e [7] in the following ultimate result, culminating the series [6], [12] and [16]. Theorem C Let G be a K -free graph of order n. If δ(G) > n/3, then χ(G) ≤ 4. 3 This theorem essentially concludes the study of ψ(n,2,h). Although there are still unsettled questions about 4-chromatic K -free graphs G of order n with δ(G) > n/3, the broad picture is 3 already fixed. The goal of this paper is to conclude likewise the study of ψ(n,r,h) for r ≥ 3. To this end, in Section 3.1, we extend the example of Hajnal and show that ψ(n,r,h) = (1−2/(2r −1))n−o(n). (2) 2 for every h > r +2. This is to say, for every ε there exists a K -free graph of order n with r+1 2 δ(G) > 1− −ε n (cid:18) 2r−1 (cid:19) and arbitrary large chromatic number, provided n is sufficiently large. We believe that for r ≥ 3 this extension is not widely known, although its main idea is the same as for r = 2. Thus, from this point on, we are concerned mainly with the question: how large can be χ(G) of a K -free graph G of order n with δ(G) > (1−2/(2r−1))n. To give the reader an immediate r+1 clue we first state an extension of Theorem C. Theorem 1 Let r ≥ 2 and G be a K -free graph of order n. If r+1 2 δ(G) > 1− n, (cid:18) 2r −1(cid:19) then χ(G) ≤ r +2. This theorem leaves only two cases of χ(G) to investigate, viz., χ(G) = r+1 and χ(G) = r+2. As one can expect, when δ(G) is sufficiently large, we have χ(G) = r +1. The precise statement extends Theorem A as follows. Theorem 2 Let r ≥ 2, 1 ≤ k ≤ 9, and let G be a K -free graph of order n. If r+1 2k −1 δ(G) > 1− n (cid:18) (2k −1)r −k +1(cid:19) then G is homomorphic to A +K . k r−2 As a corollary, under the premises of Theorem 2, we find that χ(G) ≤ r+1. Also Theorem 2 is best possible in the following sense: for every k and n there exists a (r +1)-chromatic K -free G r+1 of order n with 2k −1 δ(G) ≥ 1− n−1 (cid:18) (2k −1)r −k +1(cid:19) that is not homomorphic to A +K . This example is given in Section 3.3. k r−2 We also generalize the example of H¨aggkvist, constructing for every n an (r +2)-chromatic, K -free graph G with r+1 19 δ(G) ≥ 1− n−1, (cid:18) 19r −9(cid:19) which shows that the conclusion of Theorem 2 does not necessarily hold for k ≥ 10. This example is given in Section 3.2. To give some further structural information, we extend Theorem C as follows. 3 Theorem 3 Let r ≥ 2 and G be a K -free graph of order n with r+1 2 δ(G) > 1− n. (cid:18) 2r −1(cid:19) If χ(G) ≥ r+2, then M +K ⊂ G. If χ(G) ≤ r +1 and 3 r−2 2k −1 δ(G) > 1− n (cid:18) (2k −1)r −k +1(cid:19) then G is homomorphic to A +K . k r−2 This result is best possible in view of the examples described prior to Theorem 3. For r ≥ 3 we obtain the following summary for ψ(n,r,h) : (1−3/(3r−1))n−1 ≤ ψ(n,r,r +1) ≤ (1−3/(3r −1))n (1−19/(19r−9))n−1 ≤ ψ(n,r,r +2) ≤ (1−19/(19r−9))n ψ(n,r,h) = (1−2/(2r−1))n−o(n) for all h > r +2. About the proof method We deduce the proofs of Theorems 1, 2 and 3 by induction on r from Theorems C, A and B respectively. Although this method seems simple and natural, to our best knowledge none of Theorems 1, 2 and 3 has been mentioned in the existing literature. The same is true for the extensions of the examples of Hajnal, H¨aggkvist and Andr´asfai. The induction step, carried uniformly in all the three proofs, is based on the crucial Lemma 4. This lemma can be applied immediately to extend other results about triangle-free graphs, but we leave these extensions to the interested reader. 2 Proofs For a graph G and a vertex u ∈ V (G) we write Γ(u) for the set of neighbors of u, and d (u) for G |Γ(u)|. If U is a subgraph of G, we set- Γ(U) = ∩ Γ(x) and d(U) = |Γ(U)|; note that this is x∈U not the usual definition. Our main proof device is the following lemma. Lemma 4 Let r ≥ 3 and G be a maximal K -free graph of order n. If r+1 2 δ(G) > 1− n, (cid:18) 2r −1(cid:19) then G has a vertex u such that e(G′ ) = 0. u 4 Proof For short, set δ = δ(G) and V = V (G). Write δ′(H) for the minimum nonzero vertex degree in a graph H, and set δ′ = min{δ′(G ) : u ∈ V}. u We start with two facts which will be used several times throughout the proof. First, for every set S of s ≤ r −1 vertices, we have d(S) ≥ d(v)−(s−1)n ≥ sδ −(s−1)n ≥ (r −1)δ −(r −2)n Xv∈S ≥ (r −1)(1−2/(2r−1))n−(r −2)n = n/(2r−1) > 0; thus, every clique is contained in an r-clique. Second, since G is a maximal K -free graph, there is an (r −1)-clique in the common neigh- r+1 borhood Γ(uw) of every two nonadjacent vertices u and w. Now, for a contradiction, assume the conclusion of the lemma false: let E(G′ ) 6= ∅ for every u u ∈ V (G). For convenience the first part of the proof is split into separate claims. Claim 5 For every edge uv ∈ E(G) we have d(uv) ≤ (r −2)(n−δ)−δ′. Proof Let uv ∈ E(G), select an (r −1)-clique R containing uv, and let w ∈ Γ(R). Since G is K -free, Γ(R) is an independent set, and so Γ(R) ⊂ G′ . It is easy to see that G′ contains at r+1 w w least δ′ vertices which do not belong to Γ(R). Indeed, by assumption G′ contains edges. If some of w this edges contains a vertex t ∈ Γ(R), we have ΓG′w (t)∩Γ(R) = ∅, and the assertion follows since dG′w (t) ≥ δ′. If no edge of G′w is incident to Γ(R), there are at least δ′+1 vertices of G′w which do not belong to Γ(R). Hence, ′ ′ d(R) ≤ n−d(w)−δ ≤ n−δ −δ . Letting S = R−u−v, we have d(S) ≥ (r −3)δ −(r −4)n, and so ′ n−δ −δ ≥ d(R) ≥ d(uv)+d(S)−n ≥ d(uv)−(r −3)(n−δ), 2 as claimed. Claim 6 For every u ∈ V and w ∈ V(G′ ) we have u d(uw) ≥ d(u)+d(w)−(r −1)(n−δ). Proof Since G is a maximal K -free graph, we can select an (r−1)-clique R ⊂ Γ(uw). Since G is r+1 K -freewe have Γ(u)∩ Γ(R) = ∅ andΓ(w)∩ Γ(R) = ∅, implying that Γ(u)∪Γ(w) ⊂ V\Γ(R), r+1 and so, d(uw) = |Γ(u)∩Γ(w)| = |Γ(u)|+|Γ(w)|−|Γ(u)∪Γ(w)| ≥ d(u)+d(w)−|V\Γ(R)| = d(u)+d(w)−n+d(R) ≥ d(u)+d(w)−(r −1)(n−δ), 2 completing the proof. 5 Claim 7 For every vertex u ∈ V the graph G′ is triangle-free. u Proof Assume the opposite: let u ∈ V and T be a triangle in G′ with vertices v ,v ,v . Using u 1 2 3 Claim 6, we have d(T) = |Γ(v )∩Γ(v )∩Γ(v )| ≥ |Γ(v )∩Γ(v )∩Γ(v )∩Γ(u)| 1 2 3 1 2 3 ≥ d(v u)+d(v u)+d(v u)−2d(u) 1 2 3 ≥ 3(d(u)−(r −1)(n−δ))+d(v )+d(v )+d(v )−2d(u) 1 2 3 ≥ d(u)+3rδ−3(r −1)n ≥ (3r+1)δ −3(r−1)n. Select an r-clique R containing T, and let S = R−v −v −v . We have 1 2 3 d(S) ≥ (r −3)δ −(r −4)n, and hence, d(R) ≥ d(T)+d(S)−n > (3r+1)δ −3(r −1)n+(r −3)δ −(r −3)n 2r−3 ≥ (4r−2)δ −(4r−6)n > (4r−2) n−(4r −6)n = 0. (cid:18)2r−1(cid:19) Therefore d(R) > 0, and so, K ⊂ G, a contradiction completing the proof of the claim. 2 r+1 Let u ∈ V and vw ∈ E(G′u) be such that δ′ = dG′u(v). Since G′u is triangle-free, the set (Γ(v)∩Γ(w))\Γ(u) is empty, and so dG′u(v)+dG′u(w) = |Γ(v)\Γ(u)|+|Γ(w)\Γ(u)| = |(Γ(u)∪Γ(w))\Γ(u)| ≥ |Γ(u)∪Γ(w)|−d(u) = d(v)+d(w)−|Γ(v)∩Γ(w)|−d(u) ≥ 2δ −|Γ(v)∩Γ(w)|−d(u). Now,estimating |Γ(v)∩Γ(w)| by Claim 5, we find that ′ ′ δ +dG′u(w) ≥ 2δ −(r−2)(n−δ)+δ −d(u), and so, dG′u(w) ≥ rδ −(r −2)n−d(u). On the other hand, using Claim 6 to estimate d(uw), we see that dG′u(w) = |Γ(w)\Γ(u)| = d(w)−d(uw) ≤ d(w)−d(u)−d(w)+(r−1)(n−δ) = −d(u)+(r −1)(n−δ). Therefore, −d(u)+(r −1)(n−δ) ≥ dG′u(w) ≥ rδ −(r−2)n−d(u), 6 and so (2r−3)n ≥ (2r −1)δ, (cid:3) a contradiction, completing the proof of the lemma. Proof of Theorem 1 We shall show that G = H +G , where G is an (r −2)-partite graph, and 0 0 H is a K -free graph with δ(H) > |H|/3. We shall prove this assertion by induction on r. For r = 2 3 there is nothing to prove, so assume that the assertion holds for r′ < r. Add some edges to make G maximal K -free; δ(G) can only increase, and G remains K -free. Lemma 4 implies that there r+1 r+1 is a vertex u ∈ V (G) such that G is empty. This means that G is homomorphic to G +N, where u u N is the graph induced by the neighbors of u, which is obviously K -free. We also have r 2 2 δ(N) ≥ δ +d(u)−n > d(u)− n > d(u)− δ 2r−1 2r−3 2 ≥ 1− |N|. (cid:18) 2r −3(cid:19) By the induction hypothesis, N is a join of an (r −3)-partite graph N , and a K -free graph H 0 3 with δ(H) > |H|/3. Thus G = H+(N +G ), completing the induction step and the proof of the 0 u assertion. Since χ(H) ≤ 4, it follows that χ(G) ≤ χ(H)+r −2 ≤ r +2, completing the proof. 2 Proof of Theorem 2 In this case we shall show that G = H +G , where G is an (r −2)-partite 0 0 graph, and H is a K -free graph with 3 k +1 δ(H) > |H|. 2k +1 This assertion follows as in the proof of Theorem 1. The only difference is given in the following calculation 2k −1 δ(N) ≥ δ +d(u)−n > d(u)− n (2k −1)r −k +1 1 ≥ d(u)− δ (2k −1)(r −1)−k +1 1 ≥ 1− |N|. (cid:18) (2k −1)(r−1)−k +1(cid:19) According to Theorem A, H is homomorphic to A , and so G is homomorphic to A + K , k k r−2 2 completing the proof. The proof of Theorem 3 is the same as of Theorem 2, so we shall omit it. 3 Extension of some basic examples Below we construct three types of graphs by the same simple method: we take the join of a known K -free graph and the (r −2)-partite Tura´n graph. Choosing appropriately the order of the two 3 graphs, the resulting graph can be made almost regular. 7 3.1 Extending the example of Hajnal In this section we shall construct, for every r ≥ 2, h > 1, ε > 0 and n sufficiently large, a K -free r+1 graph G of order n with 2 δ(G) > 1− −ε n (3) (cid:18) 2r−1 (cid:19) and χ(G) > h. We start by an updated version of the example of Hajnal, reported in [9]: a K -free graph G of 3 order n with arbitrary large chromatic number and δ(G) > n/3−o(n). (m) Let K be a Kneser graph: its vertices are the sets S ⊂ [2m+h] of size |S| = m; two vertices 2m+h S and S are joined if S ∩ S = ∅. Clearly if m > h, the graph K(m) is K -free. Kneser [13] 1 2 1 2 2m+h 3 (m) conjectured and Lova´sz [14] proved that χ K = h+2. 2m+h (cid:16) (cid:17) Example 8 Let K be a copy of K(m) and let S ,...,S be its vertices, where t = 2m+h . Let 2m+h 1 t m n ≥ 3m+h+ 2m+h , and set (cid:0) (cid:1) m (cid:0) (cid:1) 2m+h n n = n− and k = 1 . 1 (cid:18) m (cid:19) (cid:22)3m+h(cid:23) Add additional n vertices to K in the following way: add a set A of (2m+h)k vertices, indexed 1 for convenience as v , i ∈ [2m+h], j ∈ [k], and add a set B of additional n −(2m+h)k vertices. ij 1 Now join every vertex of A to every vertex of B, and join every vertex v ∈ A to every vertex S ij l such that i ∈ S . Write H(n,m,h) for the resulting graph. l We immediately see that v(H(n,m,h)) = n and that (m) χ(H(n,m,h)) ≥ χ K = h+2. 2m+h (cid:16) (cid:17) Let us check that H (n,m,h) is K -free. Since no vertex in B is connected to a vertex in K, 3 and A and B are independent, after a brief inspection, we see that a triangle in H(n,m,h) must have an edge S S in K and a vertex v ∈ A; thus p ∈ S and p ∈ S , and so S ∩S 6= ∅, contrary i j pq i j i j to the assumption that S S is an edge in K. Hence, H(n,m,h) is K -free. i j 3 To estimate δ(H(n,m,h)) observe that every set S ∈ V (K) is joined to mk vertices of A; i every vertex from B is joined to (2m+h)k vertices of A and every vertex of A is joined to n − 1 (2m+h)k ≥ mk vertices of B. Therefore, selecting m sufficiently large with respect to h, we see that 2m+h δ(H(n,m,h)) ≥ mk = m n− /(3m+h) = n/3+o(n). (cid:22)(cid:18) (cid:18) m (cid:19)(cid:19) (cid:23) Therefore H(n,m,h) has the required properties. For r ≥ 3 we construct our graph G as a join of a properly selected graph H(n′,m′,h′) and an (r −2)-partite Tura´n graph. 8 Example 9 Let h > r; select n and m such that, for n ≥ n , we have 0 1 0 1 ε δ(H(n ,m,h−r)) > n − . 1 1 (cid:18)3 3(cid:19) Assume that 2r −1 n > n ; 0 3 set 2r −4 G = T n 1 r−2 (cid:18)(cid:22)2r −1 (cid:23)(cid:19) 2r −4 G = H n− n ,m,h−r , 2 (cid:18) (cid:22)2r −1 (cid:23) (cid:19) and let G = G +G . 1 2 Let us show that G satisfies the requirements. Since G is K -free and G is triangle-free, we 1 r−1 2 see that G is K -free. Also, we have r+1 χ(G) ≥ χ(G )+r −2 ≥ h. 2 For every v ∈ G , 1 r −3 2r −4 2r−4 d(v) = d (v)+|G | ≥ n +n− n G1 2 (cid:22)r −2 (cid:22)2r −1 (cid:23)(cid:23) (cid:22)2r−1 (cid:23) 2 ≥ n− n−1. 2r −1 On the other hand, for every v ∈ G , 2 2r −4 2r−4 1 d(v) = d (v)+|G | ≥ n + n− n −ε G2 1 (cid:22)2r −1 (cid:23) (cid:18) (cid:22)2r−1 (cid:23)(cid:19)(cid:18)3 (cid:19) 2r −4 3r 1 ε 2 rε 1 ≥ n−1+ n − = 1− − − n 2r −1 2r −1 (cid:18)3 3(cid:19) (cid:18) 2r−1 2r −1 n(cid:19) 2 > 1− −ε n. (cid:18) 2r −1 (cid:19) Hence, (3) also holds, and thus, G has the required properties. From our construction and Theorem 1 it follows that for all h > r +2, ψ(n,r,h) = (1−2/(2r −1))n−o(n). 9 3.2 Extending the example of H¨aggkvist As mentioned in the introduction, H¨aggkvist[10] constructed for every k ≥ 1, a 4-chromatic, 10k- regular graph of order 29k. For completeness we describe this example. Example 10 Partition V (G) = [n] into 11 sets [n] = A ∪...∪A ∪B ∪...∪B ∪C 1 5 1 5 such that |A | = ··· = |A | = 3k, |B | = ··· = |B | = 2k, |C| = 4k; join u ∈ A to v ∈ A if 1 5 1 5 i j i−j = ±1 mod 5; join u ∈ A to v ∈ B if i−j = ±1 mod 5; join all vertices of C to all vertices i j of ∪5 B . i=1 i Write H(k) for the resulting graph. Observe that H(k) contains the Mycielski graph M , which is K -free and 4-chromatic. In 3 3 fact, H(k) is homomorphic to M ; hence, it is K -free and 4-chromatic itself. It is obvious that 3 3 δ(H (k)) = 10k. Now we shall construct for every r ≥ 3 and every n > 19r − 9 a K -free, (r +2)-chromatic r+1 graph of order n with 19 δ > 1− n−1. (4) (cid:18) 19r−9(cid:19) Example 11 Assume that n > 19r−9; set n G = T n−29 1 r−2 (cid:18) (cid:22)19r −9(cid:23)(cid:19) n G = A , 2 k (cid:18)(cid:22)19r−9(cid:23)(cid:19) and let G = G +G . 1 2 We shall show that G satisfies the requirements. Since G is K -free and G is K -free, we see 1 r−1 2 3 that G is K -free. Also, we have r+1 χ(G) = χ(G )+r −2 = r +2. 2 For every v ∈ G , 2 n n d(v) = d (v)+|G | ≥ n−29 +10 G2 1 (cid:22)19r−9(cid:23) (cid:22)19r−9(cid:23) 19 ≥ 1− n. (cid:18) 19r−9(cid:19) 10