Cycles in graphs with large independence ratio

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.

Full Text (PDF format)

Published 15 June 2011