Journal of Combinatorics

Volume 2 (2011)

Number 1

Cycles in graphs with large independence ratio

Pages: 83 – 102



Benny Sudakov (Department of Mathematics, University of California at Los Angeles)

Jacques Verstraëte (Department of Mathematics, University of California at San Diego)


The independence ratio of agraph $G$ is defined by\[ \iota(G) := \sup_{X \subset V(G)} \frac{|X|}{\alpha(X)},\]where $\alpha(X)$ is the independence number of the subgraph of $G$ induced by $X$.The independence ratio is a relaxation of the chromatic number $\chi(G)$in the sense that $\chi(G) \geq \iota(G)$ for every graph $G$, while for many naturalclasses of graphs these quantities are almost equal. In this paper, we address two oldconjectures of Erd\H{o}s on cycles in graphs with large chromatic numberand a conjecture of Erd\H{o}s and Hajnal on graphs with infinite chromatic number.

Published 15 June 2011