Abstract
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a \(P_5\)-free graph with clique number \(\omega \ge 3\) has chromatic number at most \(\omega ^{\log _2(\omega )}\). The best previous result was an exponential upper bound \((5/27)3^{\omega }\), due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for \(P_5\), which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for \(P_5\)-free graphs, and our result is an attempt to approach that.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
If G, H are graphs, we say G is H-free if no induced subgraph of G is isomorphic to H; and for a graph G, we denote the number of vertices, the chromatic number, the size of the largest clique, and the size of the largest stable set by \(|G|, \chi (G), \omega (G),\alpha (G)\) respectively.
The k-vertex path is denoted by \(P_k\), and \(P_4\)-free graphs are well-understood; every \(P_4\)-free graph G with more than one vertex is either disconnected or disconnected in the complement [24], which implies that \(\chi (G)=\omega (G)\). Here we study how \(\chi (G)\) depends on \(\omega (G)\) for \(P_5\)-free graphs G.
The Gyárfás-Sumner conjecture [10, 25] says:
1.1 Conjecture: For every forest H there is a function f such that \(\chi (G)\le f(\omega (G))\) for every H-free graph G.
This is open in general, but has been proved [10] when H is a path, and for several other simple types of tree ([3, 11,12,13,14, 17, 19]; see [18] for a survey). The result is also known if all induced subdivisions of a tree are excluded [17].
A class of graphs is hereditary if the class is closed under taking induced subgraphs and under isomorphism, and a hereditary class is said to be \(\chi \)-bounded if there is a function f such that \(\chi (G)\le f(\omega (G))\) for every graph G in the class (thus, the Gyárfás-Sumner conjecture says that, for every forest H, the class of H-free graphs is \(\chi \)-bounded). Louis Esperet [8] made the following conjecture:
1.2 (False) Conjecture: Let \(\mathcal G\) be a \(\chi \)-bounded class. Then there is a polynomial function f such that \(\chi (G)\le f(\omega (G))\) for every \(G\in \mathcal G\).
Esperet’s conjecture was recently shown to be false by Briański, Davies and Walczak [2]. However, this raises the further question: which \(\chi \)-bounded classes are polynomially \(\chi \)-bounded? In particular, the two conjectures 1.1 and 1.2 would together imply the following, which is still open:
1.3 Conjecture: For every forest H, there exists \(c>0\) such that \(\chi (G)\le \omega (G)^c\) for every H-free graph G.
This is a beautiful conjecture. In most cases where the Gyárfás-Sumner conjecture has been proved, the current bounds are very far from polynomial, and 1.3 has been only been proved for a much smaller collection of forests (see [5, 15, 16, 20,21,22,23]). In [22] we proved it for any \(P_5\)-free tree H, but it has not been settled for any tree H that contains \(P_5\). In this paper we focus on the case \(H=P_5\).
The best previously-known bound on the chromatic number of \(P_5\)-free graphs in terms of their clique number, due to Esperet, Lemoine, Maffray, and Morel [9], was exponential:
1.4 If G is \(P_5\)-free and \(\omega (G)\ge 3\) then \(\chi (G)\le (5/27)3^{\omega (G)}\).
Here we make a significant improvement, showing a “near-polynomial” bound:
1.5 If G is \(P_5\)-free and \(\omega (G)\ge 3\) then \(\chi (G)\le \omega (G)^{\log _2(\omega (G))}\).
(The cycle of length five shows that we need to assume \(\omega (G)\ge 3\). Sumner [25] showed that \(\chi (G)\le 3\) when \(\omega (G)=2\).) Conjecture 1.3 when \(H=P_5\) is of great interest, because of a famous conjecture due to Erdős and Hajnal [6, 7], that:
1.6 Conjecture: For every graph H there exists \(c>0\) such that \(\alpha (G)\omega (G)\ge |G|^c\) for every H-free graph G.
This is open in general, despite a great deal of effort; and in view of [4], the smallest graph H for which 1.6 is undecided is the graph \(P_5\). Every forest H satisfying 1.3 also satisfies the Erdős-Hajnal conjecture, and so showing that \(H=P_5\) satisfies 1.3 would be a significant result. (See [1] for some other recent progress on this question.)
We use standard notation throughout. When \(X\subseteq V(G)\), G[X] denotes the subgraph induced on X. We write \(\chi (X)\) for \(\chi (G[X])\) when there is no ambiguity.
2 The Main Proof
We denote the set of nonnegative real numbers by \(\mathbb {R}_+\), and the set of nonnegative integers by \(\mathbb {Z}_+\). Let \(f:\mathbb {Z}_+\rightarrow \mathbb {R}_+\) be a function. We say
-
f is non-decreasing if \(f(y)\ge f(x)\) for all integers \(x,y\ge 0\) with \(y>x\ge 0\);
-
f is a binding function for a graph G if it is non-decreasing and \(\chi (H)\le f(\omega (H))\) for every induced subgraph H of G; and
-
f is a near-binding function for G if f is non-decreasing and \(\chi (H)\le f(\omega (H))\) for every induced subgraph H of G different from G.
In this section we show that if a function f satisfies a certain inequality, then it is a binding function for all \(P_5\)-free graphs. Then at the end we will give a function that satisfies the inequality, and deduce 1.5.
A cutset in a graph G is a set X such that \(G\setminus X\) is disconnected. A vertex \(v\in V(G)\) is mixed on a set \(A\subseteq V(G)\) or a subgraph A of a graph G if v is not in A and has a neighbour and a non-neighbour in A. It is complete to A if it is adjacent to every vertex of A. We begin with the following:
2.1 Let G be \(P_5\)-free, and let f be a near-binding function for G. Let G be connected, and let X be a cutset of G. Then
Proof
We may assume (by replacing X by a subset if necessary) that X is a minimal cutset of G; and so \(G\setminus X\) has at least two components, and every vertex in X has a neighbour in V(B), for every component B of \(G\setminus X\). Let B be one such component; we will prove that \(\chi (B)\le f(\omega (G)-1)+ \omega (G) f(\lfloor \omega (G)/2\rfloor )\), from which the result follows.
Choose \(v\in X\) (this is possible since G is connected), and let N be the set of vertices in B adjacent to v. Let the components of \(B\setminus N\) be \(R_1,\ldots ,R_k, S_1,\ldots ,S_\ell \), where \(R_1,\ldots ,R_k\) each have chromatic number more than \(f(\lfloor \omega (G)/2\rfloor )\), and \(S_1,\ldots ,S_\ell \) each have chromatic number at most \(f(\lfloor \omega (G)/2\rfloor )\). Let S be the union of the graphs \(S_1,\ldots ,S_\ell \); thus, \(\chi (S)\le f(\lfloor \omega (G)/2\rfloor )\). For \(1\le i\le k\), let \(Y_i\) be the set of vertices in N with a neighbour in \(V(R_i)\), and let \(Y=Y_1\cup \cdots \cup Y_k\).
(1) For \(1\le i\le k\), every vertex in \(Y_i\) is complete to \(R_i\).
Let \(y\in Y_i\). Thus, y has a neighbour in \(V(R_i)\); suppose that y is mixed on \(R_i\). Since \(R_i\) is connected, there is an edge ab of \(R_i\) such that y is adjacent to a and not to b. Now v has a neighbour in each component of \(G\setminus X\), and since there are at least two such components, there is a vertex \(u\in V(G)\setminus (X\cup V(B))\) adjacent to v. But then \(u\hbox {-}v\hbox {-}y\hbox {-}a\hbox {-}b\) is an induced copy of \(P_5\), a contradiction. This proves (1).
(2) \(\chi (Y)\le (\omega (G)-1) f(\lfloor \omega (G)/2\rfloor )\).
Let \(1\le i\le k\). Since \(f(\lfloor \omega (G)/2\rfloor )<\chi (R_i)\le f(\omega (R_i))\), and f is non-decreasing, it follows that \(\omega (R_i)>\omega (G)/2\). By (1), \(\omega (G[Y_i])+\omega (R_i)\le \omega (G)\), and so \(\omega (G[Y_i])<\omega (G)/2\). Consequently \(\chi (Y_i)\le f(\lfloor \omega (G)/2\rfloor )\), for \(1\le i\le k\). Choose \(I\subseteq \{1,\ldots ,k\}\) minimal such that \(\bigcup _{i\in I}Y_i=Y\). From the minimality of I, for each \(i\in I\) there exists \(y_i\in Y_i\) such that for each \(j\in I\setminus \{i\}\) we have that \(y_i\notin Y_j\); and so the vertices \(y_i\;(i\in I)\) are all distinct. For each \(i\in I\) choose \(r_i\in V(R_i)\). For all distinct \(i,j\in I\), if \(y_i,y_j\) are nonadjacent, then \(r_i\hbox {-}y_i\hbox {-}v\hbox {-}y_j\hbox {-}r_j\) is isomorphic to \(P_5\), a contradiction. Hence the vertices \(y_i\;(i \in I)\) are all pairwise adjacent, and adjacent to v; and so \(|I|\le \omega (G)-1\). Thus, \(\chi (Y)=\chi (\bigcup _{i\in I}Y_i)\le (\omega (G)-1)f(\lfloor \omega (G)/2\rfloor )\). This proves (2).
All the vertices in \(N\setminus Y\) are adjacent to v, and so \(\omega (G[N\setminus Y])\le \omega (G)-1\). Moreover, for \(1\le i\le k\), each vertex of \(R_i\) is adjacent to each vertex in \(Y_i\), and \(Y_i\ne \emptyset \) since B is connected, and so \(\omega (R_i)\le \omega (G)-1\). Since there are no edges between any two of the graphs \(G[N\setminus Y], R_1,\ldots ,R_k\), their union (Z say) has clique number at most \(\omega (G)-1\) and so has chromatic number at most \(f(\omega (G)-1)\). But V(B) is the union of Y, V(S) and V(Z); and so
This proves 2.1. \(\square \)
2.2 Let \(\Omega \ge 1\), and let \(f:\mathbb {Z}_+\rightarrow \mathbb {R}_+\) be non-decreasing, satisfying the following:
-
f is a binding function for every \(P_5\)-free graph H with \(\omega (H)\le \Omega \); and
-
\(f(w-1) + (w+2) f(\lfloor w/2\rfloor ) \le f(w)\) for each integer \(w> \Omega \).
Then f is a binding function for every \(P_5\)-free graph G.
Proof
We prove by induction on |G| that if G is \(P_5\)-free then f is a binding function for G. Thus, we may assume that G is \(P_5\)-free and f is near-binding for G. If G is not connected, or \(\omega (G)\le \Omega \), it follows that f is binding for G, so we assume that G is connected and \(\omega (G)>\Omega \). Let us write \(w=\omega (G)\) and \(m=\lfloor w/2\rfloor \). If \(\chi (G)\le f(w)\) then f is a binding function for G, so we assume, for a contradiction, that:
(1) \(\chi (G)>f(w-1) + (w+2)f(m)\).
We deduce that:
(2) Every cutset X of G satisfies \(\chi (X)> 2f(m)\).
If some cutset X satisfies \(\chi (X)\le 2f(m)\), then since \(\chi (G\setminus X)\le f(w-1)+ w f(m)\) by 2.1, it follows that \(\chi (G)\le f(w-1)+(w+2)f(m)\), contrary to (1). This proves (2).
(3) If P, Q are cliques of G, both of cardinality at least w/2, then \(G[P\cup Q]\) is connected.
Suppose not; then there is a minimal subset \(X\subseteq V(G){\setminus } (P\cup Q)\) such that P, Q are subsets of different components (A, B say) of \(G\setminus X\). From the minimality of X, every vertex \(x\in X\) has a neighbour in V(A) and a neighbour in V(B). If x is mixed on A and mixed on B, then since A is connected, there is an edge \(a_1a_2\) of A such that x is adjacent to \(a_1\) and not to \(a_2\); and similarly there is an edge \(b_1b_2\) of B with x adjacent to \(b_1\) and not to \(b_2\). But then \(a_2\hbox {-}a_1\hbox {-}x\hbox {-}b_1\hbox {-}b_2\) is an induced copy of \(P_5\), a contradiction; so every \(x\in X\) is complete to at least one of A, B. The set of vertices in X complete to A is also complete to P, and hence has clique number at most m, and hence has chromatic number at most f(m); and the same for B. Thus, \(\chi (X)\le 2f(m)\), contrary to (2). This proves (3).
If \(v\in V(G)\), we denote its set of neighbours by N(v), or \(N_G(v)\). Let \(a\in V(G)\), and let B be a component of \(G{\setminus } (N(a)\cup \{a\})\); we will show that \(\chi (B)\le (w-m+2)f(m)\).
A subset Y of V(B) is a joint of B if there is a component C of \(B{\setminus } Y\) such that \(\chi (C)> f(m)\) and Y is complete to C. If \(\emptyset \) is not a joint of B then \(\chi (B)<f(m)\) and the claim holds, so we may assume that \(\emptyset \) is a joint of B; let Y be a joint of B chosen with Y maximal, and let C be a component of \(B\setminus Y\) such that \(\chi (C)> f(m)\) and Y is complete to C.
(4) If \(v\in N(a)\) has a neighbour in V(C), then \(\chi (V(C)\setminus N(v))\le f(m)\).
Let \(N_C(v)\) be the set of neighbours of v in V(C), and \(M=V(C)\setminus N_C(v)\); and suppose that \(\chi (M)> f(m)\). Let \(C'\) be a component of G[M] with \(\chi (C')> f(m)\), and let Z be the set of vertices in \(N_C(v)\) that have a neighbour in \(V(C')\). Thus, \(Z\ne \emptyset \), since \(N_C(v),V(C')\ne \emptyset \) and C is connected. If some \(z\in Z\) is mixed on \(C'\), let \(p_1p_2\) be an edge of \(C'\) such that z is adjacent to \(p_1\) and not to \(p_2\); then \(a\hbox {-}v\hbox {-}z\hbox {-}p_1\hbox {-}p_2\) is an induced copy of \(P_5\), a contradiction. So every vertex in Z is complete to \(V(C')\); but also every vertex in Y is complete to V(C) and hence to \(V(C')\), and so \(Y\cup Z\) is a joint of B, contrary to the maximality of Y. This proves (4).
(5) \(\chi (Y)\le f(m)\) and \(\chi (C)\le (w-m+1) f(m)\).
Let X be the set of vertices in N(a) that have a neighbour in V(C). Since C is a component of \(B\setminus Y\) and hence a component of \(G{\setminus } (X\cup Y)\), and a belongs to a different component of \(G\setminus (X\cup Y)\), it follows that \(X\cup Y\) is a cutset of G. By (2), \(\chi (X\cup Y)>2f(m)\). Since \(\omega (C)\ge m+1\) (because \(\chi (C)>f(m)\), and f is near-binding for G) and every vertex in Y is complete to V(C), it follows that \(\omega (G[Y])\le w-m-1\le m\), and so has chromatic number at most f(m) as claimed; and so \(\chi (X)>f(m)\). Consequently there is a clique \(P\subseteq X\) with cardinality \(w-m\). The subgraph induced on the set of vertices of C complete to P has clique number at most m, and so has chromatic number at most f(m); and for each \(v\in P\), the set of vertices of C nonadjacent to v has chromatic number at most f(m) by (4). Thus, \(\chi (C)\le (|P|+1)f(m)= (w-m+1)f(m)\). This proves (5).
(6) \(\chi (B)\le (w-m+2) f(m)\).
By (3), every clique contained in \(V(B){\setminus } (V(C)\cup Y)\) has cardinality less than w/2 (because it is anticomplete to the largest clique of C) and so
and hence \(\chi (B\setminus Y)\le (w-m+1)f(m)\) by (5), since there are no edges between C and \(V(B)\setminus (V(C)\cup Y)\). But \(\chi (Y)\le f(m)\) by (5), and so \(\chi (B)\le (w-m+2) f(m)\). This proves (6).
By (6), \(G\setminus N(a)\) has chromatic number at most \((w-m+2)f(m)\). But G[N(a)] has clique number at most \(w-1\) and so chromatic number at most \(f(w-1)\); and so \(\chi (G)\le f(w-1)+(w-m+2)f(m)\), contrary to (1). This proves 2.2. \(\square \)
Now we deduce 1.5, which we restate:
2.3 If G is \(P_5\)-free and \(\omega (G)\ge 3\) then \(\chi (G)\le \omega (G)^{\log _2(\omega (G))}\).
Proof
Define \(f(0)=0\), \(f(1)=1\), \(f(2)=3\), and \(f(x)=x^{\log _2(x)}\) for every real number \(x\ge 3\). Let G be \(P_5\)-free. If \(\omega (G)\le 2\) then \(\chi (G)\le 3=f(2)\), by a result of Sumner [25]; if \(\omega (G) = 3\) then \(\chi (G)\le 5\le f(3)\), by an application of the result 1.4 of Esperet, Lemoine, Maffray, and Morel [9]; and if \(\omega (G)=4\) then \(\chi (G)\le 15\le f(4)\), by another application of 1.4. Consequently every \(P_5\)-free graph G with clique number at most four has chromatic number at most \(f(\omega (G))\).
We claim that
for each integer \(x>4\). If that is true, then by 2.2 with \(\Omega =4\), we deduce that \(\chi (G)\le f(\omega (G))\) for every \(P_5\)-free graph G, and so 1.5 holds. Thus, it remains to show that
for each integer \(x>4\). This can be verified by direct calculation when \(x=5\), so we may assume that \(x\ge 6\).
The derivative of \(f(x)/x^4\) is
and so is nonnegative for \(x\ge 4\). Consequently
for \(x\ge 5\). Since \(x^2(x^2-2x-4)\ge (x-1)^4\) when \(x\ge 5\), it follows that
that is,
when \(x\ge 5\). But when \(x\ge 6\) (so that f(x/2) is defined and the first equality below holds), we have
and so
when \(x\ge 6\). This proves 2.3. \(\square \)
References
Blanco, P., Bucić, M.: “Towards the Erdős–Hajnal conjecture for \(P_5\)-free graphs”, manuscript, September (2022)
Briański, M., Davies, J., Walczak, B.: Separating polynomial \(\chi \)-boundedness from \(\chi \)-boundedness. arXiv:2201.08814 (2022). https://doi.org/10.48550/arXiv.2201.08814
Chudnovsky, M., Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. XII. Distant stars. J. Graph Theory 92, 237–254 (2019)
Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Erdős-Hajnal for graphs with no 5-hole. Proceedings of the London Math. Soc. 126, 997–1014, arXiv:2102.04994 (2023). https://doi.org/10.1112/plms.12504
Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number VI Adding a four-vertex path. Eur. J. Combinatorics (2022). https://doi.org/10.48550/arXiv.2202.10412
Erdős, P., Hajnal, A.: “On spanned subgraphs of graphs”, Graphentheorie und Ihre Anwendungen (Oberhof, 1977)
Erdős, P., Hajnal, A.: Ramsey-type theorems. Discrete Appl. Math. 25, 37–52 (1989)
Esperet, L.: Graph Colorings, Flows and Perfect Matchings, Habilitation thesis, Université Grenoble Alpes (2017), 24, https://tel.archives-ouvertes.fr/tel-01850463/document
Esperet, L., Lemoine, L., Maffray, F., Morel, G.: The chromatic number of \(\{P_5, K_4\}\)-free graphs. Discrete Math. 313, 743–754 (2013)
Gyárfás, A.: On Ramsey covering-numbers. Infinite Finite Sets 2, 801–816 (1975)
Gyárfás, A.: Problems from the world surrounding perfect graphs. Proceedings of the International Conference on Combinatorial Analysis and its Applications, (Pokrzywna, 1985), Pokrzywna Zastos. Mat. 19, 413–441 (1987)
Gyárfás, A., Szemerédi, E., Tuza, Zs.: Induced subtrees in graphs of large chromatic number. Discrete Math 30, 235–344 (1980)
Kierstead, H.A., Penrice, S.G.: Radius two trees specify \(\chi \)-bounded classes. J. Graph Theory 18, 119–129 (1994)
Kierstead, H.A., Zhu, Y.: Radius three trees in graphs with large chromatic number. SIAM J. Disc. Math. 17, 571–581 (2004)
Liu, X., Schroeder, J., Wang, Z., Yu, X.: Polynomial \(\chi \)-binding functions for \(t\)-broom-free graphs. arXiv:2106.08871 (2021). https://doi.org/10.48550/arXiv.2106.08871
Schiermeyer, I., Randerath, B.: Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey. Graphs Combinatorics 35, 1–31 (2019)
Scott, A.: Induced trees in graphs of large chromatic number. J. Graph Theory 24, 297–311 (1997)
Scott, A., Seymour, P.: A survey of \(\chi \)-boundedness. J. Graph Theory 95, 473–504 (2020a)
Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. XIII. New brooms. Eur. J. Combinatorics 84, 103024 (2020b)
Scott, A., Seymour, P.: Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph. arXiv:2202.05557 (2022). https://doi.org/10.48550/arXiv.2202.05557
Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number. II. Excluding a star-forest. J. Graph Theory 101, 318–322 (2022a). arXiv:2107.11780
Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number. III. Excluding a double star. J. Graph Theory 101, 323–340 (2022b)
Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number I Excluding a biclique and an induced tree. J. Graph Theory 102(3), 458–471 (2023)
Seinsche, D.: On a property of the class of \(n\)-colorable graphs. J. Combin. Theory, Ser. B 16, 191–193 (1974)
Sumner, D.P.: Subtrees of a graph and chromatic number. In: Chartrand, G. (ed.) The Theory and Applications of Graphs, pp. 557–576. Wiley, New York (1981)
Funding
Alex Scott: Research supported by EPSRC grant EP/V007327/1. Paul Seymour: Supported by AFOSR grant FA9550-22-1-0234, and by NSF grant DMS-2154169. Sophie Spirkl: We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) [numéro de référence RGPIN-2020-03912].
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Scott, A., Seymour, P. & Spirkl, S. Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path. Combinatorica 43, 845–852 (2023). https://doi.org/10.1007/s00493-023-00015-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-023-00015-w