Google Research

Excluding hooks and their complements

Electr. J. Comb. (2018)

Abstract

The celebrated Erdos-Hajnal conjecture states that for every n-vertex undirected graph H there exists $\eps(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^{\eps(H)}$. A weaker version of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both H and its complement $H^{\compl}$. We show that the weaker conjecture holds if H is any path with a pendant edge at its third vertex; thus we give a new infinite family of graphs for which the conjecture holds.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work