The Erdős-Hajnal Conjecture for Paths and Antipaths

preprint2014arXivOpen access

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}$ .

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.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

The Erdős-Hajnal Conjecture for Paths and Antipaths

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0