Back to Search
Start Over
A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω.
- Source :
-
Journal of Graph Theory . Jan2016, Vol. 81 Issue 1, p30-34. 5p. - Publication Year :
- 2016
-
Abstract
- In 1998 the second author proved that there is an ε > 0 such that every graph satisfies ≤ [(1 - ε)(Δ+ 1) + εω]. The first author recently proved that any graph satisfying ω > 23 (Δ + 1) contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATHEMATICAL equivalence
*GRAPHIC methods
*GRAPH theory
*SET theory
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 03649024
- Volume :
- 81
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 111383623
- Full Text :
- https://doi.org/10.1002/jgt.21858