pith. sign in

arxiv: 1508.00634 · v2 · pith:5TQJNTNFnew · submitted 2015-08-04 · 🧮 math.CO

Excluding hooks and their complements

classification 🧮 math.CO
keywords conjecturecliqueeverygraphholdsindependentstatesvertex
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.