Excluding hooks and their complements

Krzysztof Choromanski¹ ; Dvir Falik² ; Anita Liebenau³ ; Viresh Patel⁴ ; Marcin Pilipczuk⁵

¹Google Brain Robotics New York
²Commogee Ltd
³UNSW
⁴Universiteit van Amsterdam
⁵University of Warsaw

The electronic journal of combinatorics, Tome 25 (2018) no. 3

Résumé

The long-standing Erdős-Hajnal conjecture states that for every $n$-vertex undirected graph $H$ there exists $\epsilon(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{\epsilon(H)}$. A natural weakening of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^\mathrm{c}$. These conjectures have been shown to hold for only a handful of graphs: it is not even known if they hold for all graphs on $5$ vertices.In a recent breakthrough, the symmetrized version of the Erdős-Hajnal conjecture was shown to hold for all paths. The goal of this paper is to show that the symmetrized conjecture holds for all trees on $6$ (or fewer) vertices. In fact this is a consequence of showing that the symmetrized conjecture holds for any path with a pendant edge at its third vertex; thus we also give a new infinite family of graphs for which the symmetrized conjecture holds.

Détail

DOI : 10.37236/6397

Classification : 05C35, 05C05, 05C75, 05D99