Abstract

Erdős and Hajnal conjectured that, for every graph HH, there exists a constant cHc_H such that every graph GG on nn vertices which does not contain any induced copy of HH has a clique or a stable set of size ncHn^{c_H}. We prove that for every kk, there exists ck>0c_k>0 such that every graph GG on nn vertices not inducing a cycle of length at least kk nor its complement contains a clique or a stable set of size nckn^{c_k}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.