An official website of the United States government
Abstract In 1977, Erd̋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 $$ \begin{align*} &2^{c\sqrt{\log |G|\log\log|G|}}.\end{align*} $$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Abstract A graphGisH-freeif it has no induced subgraph isomorphic toH. 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.more » « less
-
Abstract The Erdős–Hajnal conjecture says that for every graph there exists such that every graph not containing as an induced subgraph has a clique or stable set of cardinality at least . We prove that this is true when is a cycle of length five. We also prove several further results: for instance, that if is a cycle and is the complement of a forest, there exists such that every graph containing neither of as an induced subgraph has a clique or stable set of cardinality at least .more » « less
-
Abstract Aholein a graph is an induced cycle of length at least four, and a ‐multiholein is the union of pairwise disjoint and nonneighbouring holes. It is well known that if does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer , if does not contain a ‐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 ‐bounded.more » « less
-
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.more » « lessFree, publicly-accessible full text available July 1, 2026
-
Menger's well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger's theorem, when the k paths are required to be pairwise at some distance at least d. The result is known for k ≤ 2, but we will show that it is false for all k ≥ 3, even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2.more » « lessFree, publicly-accessible full text available July 1, 2026
-
Free, publicly-accessible full text available February 1, 2026
-
We prove that for every path , and every integer , there is a polynomial such that every graph with chromatic number greater than either contains as an induced subgraph, or contains as a subgraph the complete ‐partite graph with parts of cardinality . For and general this is a classical theorem of Gyárfás, and for and general this is a theorem of Bonamy et al.more » « less
