Contents Online

# 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

#### 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.