The Erdős-Hajnal Conjecture for Paths and Antipaths
arXiv:1303.5205 · doi:10.1016/j.jctb.2015.01.001
Abstract
We prove that for every k, there exists such that every graph G on n vertices not inducing a path and its complement contains a clique or a stable set of size .