Journal of Combinatorics

Volume 2 (2011)

Number 1

Cycles in graphs with large independence ratio

Pages: 83 – 102

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n1.a3

Authors

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

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

Abstract

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)