Excluding hooks and their complements
The electronic journal of combinatorics, Tome 25 (2018) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/6397
Classification : 05C35, 05C05, 05C75, 05D99

Krzysztof Choromanski  1   ; Dvir Falik  2   ; Anita Liebenau  3   ; Viresh Patel  4   ; Marcin Pilipczuk  5

1 Google Brain Robotics New York
2 Commogee Ltd
3 UNSW
4 Universiteit van Amsterdam
5 University of Warsaw
@article{10_37236_6397,
     author = {Krzysztof Choromanski and Dvir Falik and Anita Liebenau and Viresh Patel and Marcin Pilipczuk},
     title = {Excluding hooks and their complements},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {3},
     doi = {10.37236/6397},
     zbl = {1395.05085},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6397/}
}
TY  - JOUR
AU  - Krzysztof Choromanski
AU  - Dvir Falik
AU  - Anita Liebenau
AU  - Viresh Patel
AU  - Marcin Pilipczuk
TI  - Excluding hooks and their complements
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6397/
DO  - 10.37236/6397
ID  - 10_37236_6397
ER  - 
%0 Journal Article
%A Krzysztof Choromanski
%A Dvir Falik
%A Anita Liebenau
%A Viresh Patel
%A Marcin Pilipczuk
%T Excluding hooks and their complements
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6397/
%R 10.37236/6397
%F 10_37236_6397
Krzysztof Choromanski; Dvir Falik; Anita Liebenau; Viresh Patel; Marcin Pilipczuk. Excluding hooks and their complements. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/6397

Cité par Sources :