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
Trees and near-linear stable sets
When H is a forest, the Gyárfás-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-0(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 is a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a “fractional colouring” version of the Gyárfás-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.
more »
« less
- Award ID(s):
- 2154169
- PAR ID:
- 10688387
- Publisher / Repository:
- Springer Nature Link
- Date Published:
- Journal Name:
- Combinatorica
- Volume:
- 45
- Issue:
- 5
- ISSN:
- 0209-9683
- Subject(s) / Keyword(s):
- Gyárfás-Sumner conjecture
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 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.more » « less
-
A $$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ős and Székely 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ős-Székely 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)$.more » « less
-
A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.more » « less
-
We prove that for every complete graph Kt , all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/polylog |G|. This is close to best possible, because for t ≥7, not all such graphs G have a stable set of linear size, even if G is triangle-free.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1007/s00493-025-00177-9
