The ErdH{o}s-Hajnal Conjecture for Paths and Antipaths
classification
🧮 math.CO
cs.DM
keywords
everyantipathscliquecomplementconjecturecontainsexistsgraph
read the original abstract
We prove that for every k, there exists $c_k>0$ such that every graph G on n vertices not inducing a path $P_k$ and its complement contains a clique or a stable set of size $n^{c_k}$.
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.