Cycles in Sparse Graphs II

Details Cycles in Sparse Graphs II Cycles in Sparse Graphs II

2010-10-26

arxiv.org/abs/1010.5309v1

Mathematics

Combinatorics

16 pages, 1 figure

Scientific paper

The {\em independence ratio} of a graph $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 natural classes of graphs these quantities are almost equal. In this paper, we address two old conjectures of Erd\H{o}s on cycles in graphs with large chromatic number and a conjecture of Erd\H{o}s and Hajnal on graphs with infinite chromatic number.

Affiliated with

Also associated with

No associations

Rating

Cycles in Sparse Graphs II does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cycles in Sparse Graphs II, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cycles in Sparse Graphs II will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159087