A graph
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|, χ(G), ω(G), α(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 χ(G) = ω(G). Here we study how χ(G) depends on ω(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 χ(G) ≤ f (ω(G)) for every
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 χ-bounded if there is a function f such that χ(G) ≤ f (ω(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 χ-bounded). Louis Esperet [8] made the following conjecture:
Esperet's conjecture was recently shown to be false by Briański, Davies and Walczak [2]. However, this raises the further question: which χ-bounded classes are polynomially χ-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 χ(G) ≤ ω(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 [15,20,22,23,21,5,16]). In [23] 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:
Here we make a significant improvement, showing a "near-polynomial" bound:
(The cycle of length five shows that we need to assume ω(G) ≥ 3. Sumner [25] showed that χ(G) ≤ 3 when ω(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 α(G)ω(G) ≥ |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 ⊆ V (G), G[X] denotes the subgraph induced on X. We write χ(X) for χ(G[X]) when there is no ambiguity.
We denote the set of nonnegative real numbers by R + , and the set of nonnegative integers by Z + . Let f : Z + → R + be a function. We say
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.
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 \ X has at least two components, and every vertex in X has a neighbour in V (B), for every component B of G \ X. Let B be one such component; we will prove that
), from which the result follows.
Choose v ∈ 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 \ N be R 1 , . . . , R k , S 1 , . . . , S ℓ , where R 1 , . . . , R k each have chromatic number more than f (⌊ω(G)/2⌋), and S 1 , . . . , S ℓ each have chromatic number at most f (⌊ω(G)/2⌋). Let S be the union of the graphs S 1 , . . . , S ℓ ; thus,
Let y ∈ 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 \ X, and since there are at least two such components, there is a vertex u ∈ V (G) \ (X ∪ V (B)) adjacent to v. But then u-v-y-a-b is an induced copy of P 5 , a contradiction. This proves (1).
( 2)
From the minimality of I, for each i ∈ I there exists y i ∈ Y i such that for each j ∈ I \ {i} we have that y i / ∈ Y j ; and so the vertices y i (i ∈ I) are all distinct. For each i ∈ I choose r i ∈ V (R i ). For all distinct i, j ∈ I, if y i , y j are nonadjacent, then r i -y i -v-y j -r j is isomorphic to P 5 , a contradiction. Hence the vertices y i (i ∈ I) are all pairwise adjacent, and adjacent to v; and so |I| ≤ ω(G) -1.
All the vertices in N \ Y are adjacent to v, and so
Since there are no edges between any two of the graphs G[N \ Y ], R 1 , . . . , R k , their union (Z say) has clique number at most ω(G) -1 and so has chromatic number at most f (ω(G) -1). But V (B) is the union of Y, V (S) and V (Z); and so
This proves 2.1.
Let Ω ≥ 1, and let f : Z + → R + be non-decreasing, satisfying the following:
• f is a binding function for every P 5 -free graph H with ω(H) ≤ Ω; and
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 ω(G) ≤ Ω, it follows that f is binding for G, so we assume that G is connected and ω(G) > Ω. Let us write w = ω(G) and m = ⌊w/2⌋. If χ(G) ≤ f (w) then f is a binding function for G, so we assume, for a contradiction, that:
(1) χ(G) > f (w -1) + (w + 2)f (m).
We deduce that:
(2) Every cutset X of G satisfies χ(X) > 2f (m).
If some cutset X satisfies χ(X) ≤ 2f (m), then since χ(G \ X) ≤ f (w -1) + wf (m) by 2.1, it follows that χ(G) ≤ 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 ∪ Q] is connected.
Suppose not; then there is a minimal subset X ⊆ V (G) \ (P ∪ Q) such that P, Q are subsets of different components (A, B say) of G \ X. From the minimality of X, every vertex x ∈ 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 1 a 2 of A such that x is adjacent to a 1 and not to a 2 ; and similarly there is an edge b 1 b 2 of B with x adjacent to b 1 and not to b 2 . But then a 2 -a 1 -x-b 1 -b 2 is an induced copy of P 5 , a contradiction; so every x ∈ 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, χ(X) ≤ 2f (m), contrary to (2). This proves (3).
and the claim holds, so we may assume that ∅ is a joint of B; let Y be a joint of B chosen with Y maximal, and let
Let N C (v) be the set of neighbours of v in V (C), and M = V (C) \ N C (v); and suppose that χ(M ) > f (m). Let C ′ be a component of G[M ] with χ(C ′ ) > f (m), and let Z be the set of vertices in N C (v) that have a neighbour in V (C ′ ). Thus, Z ̸ = ∅, since N C (v), V (C ′ ) ̸ = ∅ and C is connected. If some z ∈ Z is mixed on C ′ , let p 1 p 2 be an edge of C ′ such that z is adjacent to p 1 and not to p 2 ; then a-v-z-p 1 -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 ∪ Z is a joint of B, contrary to the maximality of Y . This proves (4).
, and f is near-binding for G) and every vertex in Y is complete to V (C), it follows that ω(G[Y ]) ≤ w -m -1 ≤ m, and so has chromatic number at most f (m) as claimed; and so χ(X) > f (m). Consequently there is a clique P ⊆ 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 ∈ P , the set of vertices of C nonadjacent to v has chromatic number at most f (m) by ( 4). Thus, χ(C) ≤ (|P | + 1)f (m) = (w -m + 1)f (m). This proves (5). 5), and so χ(B) ≤ (w -m + 2)f (m). This proves (6).
By (6), G \ 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 χ(G) ≤ f (w -1) + (w -m + 2)f (m), contrary to (1). This proves 2.2. Now we deduce 1.5, which we restate:
, by a result of Sumner [25]; if ω(G) = 3 then χ(G) ≤ 5 ≤ f (3), by an application of the result 1.4 of Esperet, Lemoine, Maffray, and Morel [9]; and if ω(G) = 4 then χ(G) ≤ 15 ≤ 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 (ω(G)).
We claim that f (x -1) + (x + 2)f (⌊x/2⌋) ≤ f (x)
for each integer x > 4. If that is true, then by 2.2 with Ω = 4, we deduce that χ(G) ≤ f (ω(G)) for every P 5 -free graph G, and so 1.5 holds. Thus, it remains to show that f (x -1) + (x + 2)f (⌊x/2⌋) ≤ f (x)
for each integer x > 4. This can be verified by direct calculation when x = 5, so we may assume that x ≥ 6.
The derivative of f (x)/x 4 is (2 log 2 (x) -4)x log 2 (x)-5 , and so is nonnegative for x ≥ 4. Consequently
for x ≥ 5. Since x 2 (x 2 -2x -4) ≥ (x -1) 4 when x ≥ 5, it follows that
that is, f (x -1) + 2x + 4 x 2 f (x) ≤ f (x), when x ≥ 5. But when x ≥ 6 (so that f (x/2) is defined and the first equality below holds), we have f (⌊x/2⌋) ≤ f (x/2) = (x/2) log 2 (x/2) = (x/2) log 2 (x)-1 = (2/x)(x/2) log 2 (x) = (2/x 2 )f (x), and so f (x -1) + (x + 2)f (⌊x/2⌋) ≤ f (x) when x ≥ 6. This proves 2.3.