Search

We give a construction to build all digraphs with the property that every directed cycle has length three.

Let G be an acyclic digraph, and let a, b, c, d be vertices, where a, b are sources, c, d are sinks, and every other vertex has in-degree and out-degree at least two. In 1985, Thomassen showed that there do not exist disjoint directed paths from a to c and from b to d, if and only if G can be drawn in a closed disc with a, b, c, d drawn in the boundary in order. We give a shorter proof.

We prove that for every complete graph $K_t$, all graphs $G$ with no induced subgraph isomorphic to a subdivision of $K_t$ have a stable subset of size at least $|G|/{\rm polylog}|G|$. This is close to best possible, because for $t\ge 6$, not all such graphs $G$ have a stable set of linear size, even if $G$ is triangle-free.

When $H$ is a forest, the Gy\'arf\'as-Sumner conjecture implies that every graph $G$ with no induced subgraph isomorphic to $H$ and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph $G$ has a stable set of size $|G|^{1-o(1)}$. If $H$ is not a forest, there need not be such a stable set. Second, we prove that when $H$ is a ``multibroom'', there {\em is} a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a ``fractional colouring'' version of the Gy\'arf\'as-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.

A {\em $k$-kernel} in a digraph $G$ is a stable set $X$ of vertices such that every vertex of $G$ can be joined from $X$ by a directed path of length at most $k$. We prove three results about $k$-kernels. First, it was conjectured by Erd\H{o}s and Sz\'ekely in 1976 that every digraph $G$ with no source has a 2-kernel $|K|$ with $|K|\le |G|/2$. We prove this conjecture when $G$ is a ``split digraph'' (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph $G$ with no source has a 2-kernel of size at most $2|G|/3$. Second, the Erd\H{o}s-Sz\'ekely conjecture implies that in every digraph $G$ there is a 2-kernel $K$ such that the union of $K$ and its out-neighbours has size at least $|G|/2$. We prove that this is true if $V(G)$ can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all $k\ge 3$, every strongly-connected digraph $G$ has a $k$-kernel of size at most about $|G|/(k+1)$. This remains open, but we prove that there is one of size at most about $|G|/(k-1)$.

The fork is the tree obtained from the claw $K_{1,3}$ by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs., Comment: This is an old paper. It was published in 2020 in Discrete Math where it was awarded Editors' choice

We prove that a graph does not contain as a minor a graph formed by 0-, 1-, 2- or 3-summing $k$ copies of $K_5$ or $K_{3,3}$, if and only if it has bounded genus.

A graph is a ``$k$-Kuratowski graph'' if it has exactly $k$ components, each isomorphic to $K_5$ or to $K_{3,3}$. We prove that if a graph $G$ contains no $k$-Kuratowski graph as a minor,then there is a set $X$ of boundedly many vertices such that $G\setminus X$ can be drawn in a (possibly disconnected) surface in which no $k$-Kuratowski graph can be drawn.

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible., Comment: 13 pages

It was conjectured, independently by two sets of authors, that for all integers $k,d\ge 1$ there exists $\ell>0$, such that if $S,T$ are subsets of vertices of a graph $G$, then either there are $k$ paths between $S,T$, pairwise at distance at least $d$, or there is a set $X\subseteq V(G)$ with $|X|\le k-1$ such that every path between $S,T$ contains a vertex with distance at most $\ell$ from some member of $X$. The result is known for $k\le 2$, but we will show that it is false for all $k\ge 3$, even if $G$ is constrained to have maximum degree at most three. We also give a proof of the result when $k=2$ that is simpler than the previous proofs.

We confirm a conjecture of Fox, Pach, and Suk, that for every $d>0$, there exists $c>0$ such that every $n$-vertex graph of VC-dimension at most $d$ has a clique or stable set of size at least $n^c$. This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erd\H{o}s-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lov\'asz and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper., Comment: 11 pages, minor revisions

We prove the Erd\H{o}s-Hajnal conjecture for the five-vertex path $P_5$; that is, there exists $c>0$ such that every $n$-vertex graph with no induced $P_5$ has a clique or stable set of size at least $n^c$. This completes the verification of the Erd\H{o}s-Hajnal property of all five-vertex graphs. Indeed, we show a stronger statement, that $P_5$ satisfies the polynomial version of a theorem of R\"odl. To achieve this, we combine simple probabilistic and structural ideas with the iterative sparsification framework introduced in the series., Comment: 15 pages

The Erd\H{o}s-Hajnal conjecture says that, for every graph $H$, there exists $c>0$ such that every $H$-free graph on $n$ vertices has a clique or stable set of size at least $n^c$. In this paper we are concerned with the case when $H$ is a path. The conjecture has been proved for paths with at most five vertices, but not for longer paths. We prove that the conjecture is ``nearly'' true for all paths: for every path $H$, all $H$-free graphs with $n$ vertices have cliques or stable sets of size at least $2^{(\log n)^{1-o(1)}}$.

Erd\H{o}s and Hajnal conjectured that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or a stable set of size at least $|G|^c$ (a graph is $H$-free if it has no induced subgraph isomorphic to $H$). Alon, Pach, and Solymosi reduced the Erd\H{o}s-Hajnal conjecture to the case when $H$ is {\em prime} (that is, $H$ cannot be obtained by vertex-substitution from smaller graphs); but until now, it was not shown for any prime graph with more than five vertices. We will provide infinitely many prime graphs that satisfy the conjecture. Let $H$ be a graph with the property that for every prime induced subgraph $G'$ with $|G'|\ge 3$, $G'$ has a vertex of degree one and a vertex of degree $|G'|-2$. We will prove that every graph $H$ with this property satisfies the Erd\H{o}s-Hajnal conjecture, and infinitely many graphs with this property are prime. More generally, say a graph is {\em buildable} if every prime induced subgraph with at least three vertices has a vertex of degree one. We prove that if $H_1$ and $\overline{H_2}$ are buildable, there exists $c>0$ such that every graph $G$ that is both $H_1$-free and $H_2$-free has a clique or a stable set of size at least $|G|^c$. Our proof uses a new technique of ``iterative sparsification'', where we pass to a sequence of successively more restricted induced subgraphs. This approach also extends to ordered graphs and to tournaments. For ordered graphs, we obtain a theorem which significantly extends a recent result of Pach and Tomon about excluding monotone paths; and for tournaments, we obtain infinitely many new prime tournaments that satisfy the Erd\H{o}s-Hajnal conjecture (in tournament form).

We show that for every two cycles $C,D$, there exists $c>0$ such that if $G$ is both $C$-free and $\overline{D}$-free then $G$ has a clique or stable set of size at least $|G|^c$. ("$H$-free" means with no induced subgraph isomorphic to $H$, and $\overline{D}$ denotes the complement graph of $D$.) Since the five-vertex cycle $C_5$ is isomorphic to its complement, this extends the earlier result that $C_5$ satisfies the Erd\H{o}s-Hajnal conjecture. It also unifies and strengthens several other results. The results for cycles are special cases of results for subdivisions, as follows. Let $H,J$ be obtained from smaller graphs by subdividing every edge exactly twice. We will prove that there exists $c>0$ such that if $G$ is both $H$-free and $\overline{J}$-free then $G$ has a clique or stable set of size at least $|G|^c$. And the same holds if $H$ and/or $J$ is obtained from a graph bychoosing a forest $F$ and subdividing every edge not in $F$ at least five times. Our proof uses the framework of iterative sparsification developed in other papers of this series. Along the way, we will also give a short and simple proof of a celebrated result of Fox and Sudakov, that says that for all $H$, every $H$-free graph contains either a large stable set or a large complete bipartite subgraph., Comment: 20 pages

A well-known theorem of R\"odl says that for every graph $H$, and every $\epsilon>0$, there exists $\delta>0$ such that if $G$ does not contain an induced copy of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge \delta|G|$ such that one of $G[X],\overline{G}[X]$ has edge-density at most $\epsilon$. But how does $\delta$ depend on $\epsilon$? Fox and Sudakov conjectured that the dependence is at most polynomial: that for all $H$ there exists $c>0$ such that for all $\epsilon$ with $0<\epsilon\le 1/2$, R\"odl's theorem holds with $\delta=\epsilon^c$. This conjecture implies the Erd\H{o}s-Hajnal conjecture, and until now it had not been verified for any non-trivial graphs $H$. Our first result shows that it is true when $H=P_4$. Indeed, in that case we can take $\delta=\epsilon$, and insist that one of $G[X],\overline{G}[X]$ has maximum degree at most $\epsilon^2|G|$). Second, we will show that every graph $H$ that can be obtained by substitution from copies of $P_4$ satisfies the Fox-Sudakov conjecture. To prove this, we need to work with a stronger property. Let us say $H$ is {\em viral} if there exists $c>0$ such that for all $\epsilon$ with $0<\epsilon\le 1/2$, if $G$ contains at most $\epsilon^c|G|^{|H|}$ copies of $H$ as induced subgraphs, then there exists $X\subseteq V(G)$ with $|X|\ge \epsilon^c|G|$ such that one of $G[X],\overline{G}[X]$ has edge-density at most $\epsilon$. We will show that $P_4$ is viral, using a ``polynomial $P_4$-removal lemma'' of Alon and Fox. We will also show that the class of viral graphs is closed under vertex-substitution. Finally, we give a different strengthening of R\"odl's theorem: we show that if $G$ does not contain an induced copy of $P_4$, then its vertices can be partitioned into at most $480\epsilon^{-4}$ subsets $X$ such that one of $G[X],\overline{G}[X]$ has maximum degree at most $\epsilon|X|$.

When does a graph admit a tree-decomposition in which every bag has small diameter? For finite graphs, this is a property of interest in algorithmic graph theory, where it is called having bounded ``tree-length''. We will show that this is equivalent to being ``boundedly quasi-isometric to a tree'', which for infinite graphs is a much-studied property from metric geometry. One object of this paper is to tie these two areas together. We will prove that there is a tree-decomposition in which each bag has small diameter, if and only if there is a map $\phi$ from $V(G)$ into the vertex set of a tree $T$, such that for all $u,v\in V(G)$, the distances $d_G(u,v), d_T(\phi(u),\phi(v))$ differ by at most a constant. A ``geodesic loaded cycle'' in $G$ is a pair $(C,F)$, where $C$ is a cycle of $G$ and $F\subseteq E(C)$, such that for every pair $u,v$ of vertices of $C$, one of the paths of $C$ between $u,v$ contains at most $d_G(u,v)$ $F$-edges, where $d_G(u,v)$ is the distance between $u,v$ in $G$. We will show that a graph $G$ admits a tree-decomposition in which every bag has small diameter, if and only if $|F|$ is small for every geodesic loaded cycle $(C,F)$. Our proof is an extension of an algorithm to approximate tree-length in finite graphs by Dourisboure and Gavoille. In metric geometry, there is a similar theorem that characterizes when a graph is quasi-isometric to a tree, ``Manning's bottleneck criterion''. The goal of this paper is to tie all these concepts together, and add a few more related ideas. For instance, we prove a conjecture of Rose McCarty, that $G$ admits a tree-decomposition in which every bag has small diameter, if and only if for all vertices $u,v,w$ of $G$, some ball of small radius meets every path joining two of $u,v,w$.

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.

Two subgraphs $A,B$ of a graph $G$ are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if $G$ is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erd\H{o}s in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all $t, c\ge 1$ there exists $d\ge 1$ such that if $G$ has chromatic number at least $d$, and does not contain the complete graph $K_t$ as a subgraph, then there are anticomplete subgraphs $A,B$, where $A$ has minimum degree at least $c$ and $B$ has chromatic number at least $c$. Second, we look at what happens if we replace the hypothesis that $G$ has sufficiently large chromatic number with the hypothesis that $G$ has sufficently large minimum degree. This, together with excluding $K_t$, is {\em not} enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of xcluding $K_t$ we exclude the complete bipartite graph $K_{t,t}$. More exactly: for all $t, c\ge 1$ there exists $d\ge 1$ such that if $G$ has minimum degree at least $d$, and does not contain the complete bipartite graph $K_{t,t}$ as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least $c$.

We prove that for every path H, and every integer d, there is a polynomial f such that every graph G with chromatic number greater than f(t) either contains H as an induced subgraph, or contains as a subgraph the complete d-partite graph with parts of cardinality t. For t = 1 and general d this is a classical theorem of Gy\'arf\'as, and for d = 2 and general t this is a theorem of Bonamy et al.

The Gy\'arf\'as-Sumner conjecture says that for every tree $T$ and every integer $t\ge 1$, if $G$ is a graph with no clique of size $t$ and with sufficiently large chromatic number, then $G$ contains an induced subgraph isomorphic to $T$. This remains open, but we prove that under the same hypotheses, $G$ contains a subgraph $H$ isomorphic to $T$ that is ``path-induced''; that is, for some distinguished vertex~$r$, every path of $H$ with one end $r$ is an induced path of $G$.

We prove that every connected $P_5$-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected $P_5$-free graph $G$ with independence number at least three contains a three-vertex induced path with vertices $a \hbox{-} b \hbox{-} c$ in order, such that every neighbour of $c$ is also adjacent to one of $a,b$., Comment: 14 pages

In 1977, Erd\H{o}s and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $ |G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We prove a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of R\"odl, Nikiforov, and the theorem of Erd\H{o}s and Hajnal mentioned above.

Let us say a graph is $s\mathcal{O}$-free, where $s\ge 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when $s=2$, is not well understood. For instance, until now we did not know how to test whether a graph is $2\mathcal{O}$-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2\mathcal{O}$-free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all $s\ge 1$, there exists $c>0$ such that every $s\mathcal{O}$-free graph $G$ has at most $|G|^c$ induced paths. This provides a poly-time algorithm to test if a graph is $s\mathcal{O}$-free, for all fixed $s$. The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, D\'epr\'es, Esperet, Geniet, Hilaire, Thomass\'e and Wesolek, that in every $s\mathcal{O}$-free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$. And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.

It takes $n^2/4$ cliques to cover all the edges of a complete bipartite graph $K_{n/2,n/2}$, but how many cliques does it take to cover all the edges of a graph $G$ if $G$ has no $K_{t,t}$ induced subgraph? We prove that $O(|G|^{2-1/(2t)})$ cliques suffice; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon.

Motivated by Hadwiger's conjecture, we prove that every $n$-vertex graph $G$ with no independent set of size three contains an $\lceil n/2\rceil$-vertex simple minor $H$ with $$0.98688 \cdot \binom{|V(H)|}{2} - o(n^2)$$ edges.

A theorem of Mader shows that every graph with average degree at least eight has a $K_6$ minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have $K_6$ minors, but minimum degree six is certainly not enough. For every $c>0$ there are arbitrarily large graphs with average degree at least $8-c$ and minimum degree at least six, with no $K_6$ minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every $c>0$ there are arbitrarily large bipartite graphs with average degree at least $8-c$ and no $K_6$ minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a $K_6$ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

A pure pair in a tournament $G$ is an ordered pair $(A,B)$ of disjoint subsets of $V(G)$ such that every vertex in $B$ is adjacent from every vertex in $A$. Which tournaments $H$ have the property that if $G$ is a tournament not containing $H$ as a subtournament, and $|G|>1$, there is a pure pair $(A,B)$ in $G$ with $|A|,|B|\ge c|G|$, where $c>0$ is a constant independent of $G$? Let us say that such a tournament $H$ has the strong EH-property. As far as we know, it might be that a tournament $H$ has this property if and only if its vertex set has a linear ordering in which its backedges form a forest. Certainly this condition is necessary, but we are far from proving sufficiency. We make a small step in this direction, showing that if a tournament can be ordered with at most three backedges then it has the strong EH-property (except for one case, that we could not decide). In particular, every tournament with at most six vertices has the property, except for three that we could not decide. We also give a seven-vertex tournament that does not have the strong EH-property. This is related to the Erdos-Hajnal conjecture, which in one form says that for every tournament $H$ there exists $\tau>0$ such that every tournament $G$ not containing $H$ as a subtournament has a transitive subtournament of cardinality at least $|G|^\tau$. Let us say that a tournament $H$ satisfying this has the EH-property. It is known that every tournament with the strong EH-property also has the EH-property; so our result extends work by Berger, Choromanski and Chudnovsky, who proved that every tournament with at most six vertices has the EH-property, except for one that they did not decide., Comment: Accepted manuscript; see DOI for journal version

A class of graphs is $\chi$-bounded if there is a function $f$ such that every graph $G$ in the class has chromatic number at most $f(\omega(G))$, where $\omega(G)$ is the clique number of $G$; the class is polynomially $\chi$-bounded if $f$ can be taken to be a polynomial. The Gy\'arf\'as-Sumner conjecture asserts that, for every forest $H$, the class of $H$-free graphs (graphs with no induced copy of $H$) is $\chi$-bounded. Let us say a forest $H$ is good if it satisfies the stronger property that the class of $H$-free graphs is polynomially $\chi$-bounded. Very few forests are known to be good: for example, it is open for the five-vertex path. Indeed, it is not even known that if every component of a forest $H$ is good then $H$ is good, and in particular, it was not known that the disjoint union of two four-vertex paths is good. Here we show the latter, and more generally, that if $H$ is good then so is the disjoint union of $H$ and a four-vertex path. We also prove a more general result: if every component of $H_1$ is good, and $H_2$ is any path (or broom) then the class of graphs that are both $H_1$-free and $H_2$-free is polynomially $\chi$-bounded., Comment: Accepted manuscript; see DOI for journal version

A hole in a graph $G$ is an induced cycle of length at least four, and a $k$-multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any $k$, if $G$ does not contain a $k$-multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially $\chi$-bounded.

The Gy\'arf\'as-Sumner conjecture says that for every forest $H$ and every integer $k$, if $G$ is $H$-free and does not contain a clique on $k$ vertices then it has bounded chromatic number. (A graph is $H$-free if it does not contain an induced copy of $H$.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: R\"odl showed that, for every forest $H$, if $G$ is $H$-free and does not contain $K_{t,t}$ as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened R\"odl's result, showing that for every forest $H$, the bound on chromatic number can be taken to be polynomial in $t$. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$, if $G$ is $H$-free and does not contain as a subgraph the complete $d$-partite graph with parts of cardinality $t$, then its chromatic number is at most polynomial in $t$.

Say a graph $G$ is a {\em pentagraph} if every cycle has length at least five, and every induced cycle of odd length has length five. N. Robertson proposed the conjecture that the Petersen graph is the only pentagraph that is three-connected and internally 4-connected, but this was disproved by M. Plummer and X. Zha in 2014. Plummer and Zha conjectured that every 3-connected, internally 4-connected pentagraph is three-colourable. We prove this: indeed, we will prove that every pentagraph is three-colourable.

A pure pair of size $t$ in a graph $G$ is a pair $A,B$ of disjoint sets of $t$ vertices such that $A$ is either complete or anticomplete to $B$. It is known that, for every forest $H$, every graph on $n\ge2$ vertices that does not contain $H$ or its complement as an induced subgraph has a pure pair of size $\Omega(n)$; furthermore, this only holds when $H$ or its complement is a forest. In this paper, we look at pure pairs of size $n^{1-c}$, where $0c$.

Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded., Comment: Accepted manuscript; see DOI for journal version

A graph is "$\ell$-holed" if all its induced cycles of length at least four have length exactly $\ell$. We give a complete description of the $\ell$-holed graphs for each $\ell\ge 7$.

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 Erdos-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.

A double star is a tree with two internal vertices. It is known that the Gy\'arf\'as-Sumner conjecture holds for double stars, that is, for every double star $H$, there is a function $f$ such that if $G$ does not contain $H$ as an induced subgraph then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Here we prove that $f$ can be chosen to be a polynomial.

The Gyarfas-Sumner conjecture says that for every forest $H$, there is a function $f$ such that if $G$ is $H$-free then $\chi(G)\le f(\omega(G))$ (where $\chi, \omega$ are the chromatic number and the clique number of $G$). Louis Esperet conjectured that, whenever such a statement holds, $f$ can be chosen to be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a modest set of forests $H$, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when $H$ is a five-vertex path. Here we prove Esperet's conjecture when each component of $H$ is a star.

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very dense or very sparse. More precisely, let us say that a graph F on n vertices is c-restricted if either F or its complement has maximum degree at most cn. Rodl proved that for every graph H, and every c>0, every H-free graph G has a linear-sized set of vertices inducing a c-restricted graph. We strengthen Rodl's result as follows: for every graph H, and all c>0, every H-free graph can be partitioned into a bounded number of subsets inducing c-restricted graphs.

A pure pair in a graph $G$ is a pair $A,B$ of disjoint subsets of $V(G)$ such that $A$ is complete or anticomplete to $B$. Jacob Fox showed that for all $\epsilon>0$, there is a comparability graph $G$ with $n$ vertices, where $n$ is large, in which there is no pure pair $A,B$ with $|A|,|B|\ge \epsilon n$. He also proved that for all $c>0$ there exists $\epsilon>0$ such that for every comparability graph $G$ with $n>1$ vertices, there is a pure pair $A,B$ with $|A|,|B|\ge \epsilon n^{1-c}$; and conjectured that the same holds for every perfect graph $G$. We prove this conjecture and strengthen it in several ways. In particular, we show that for all $c>0$, and all $\ell_1, \ell_2\ge 4c^{-1}+9$, there exists $\epsilon>0$ such that, if $G$ is a graph with $n>1$ vertices and no hole of length exactly $\ell_1$ and no antihole of length exactly $\ell_2$, then there is a pure pair $A,B$ in $G$ with $|A|\ge \epsilon n$ and $|B|\ge \epsilon n^{1-c}$. This is further strengthened, replacing excluding a hole by excluding some long subdivision of a general graph.

Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph $K_{t,t}$ as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree H, the degeneracy is at most polynomial in t. This answers a question of Bonamy, Pilipczuk, Rzazewski, Thomasse and Walczak.

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.