Cycles in Sparse Graphs II

Abstract

The {\em independence ratio} of a graph $G$ is defined by \[ ι(G) := \sup_{X \subset V(G)} \frac{|X|}{α(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)\ge \iota (G)$ for every graph $G$, while for many natural classes of graphs these quantities are almost equal. In this paper, we address two old conjectures of Erdős on cycles in graphs with large chromatic number and a conjecture of Erdős and Hajnal on graphs with infinite chromatic number.

16 pages, 1 figure