Back to Search
Start Over
GRAPHS WITH χ = Δ HAVE BIG CLIQUES.
- Source :
-
SIAM Journal on Discrete Mathematics . 2015, Vol. 29 Issue 4, p1792-1814. 23p. 3 Diagrams. - Publication Year :
- 2015
-
Abstract
- Brooks’ theorem implies that if a graph has Δ ≥ 3 and χ > Δ, then ω = Δ+1. Borodin and Kostochka conjectured that if Δ ≥ 9 and χ ≥ Δ, then ω ≥ Δ. We show that if Δ ≥ 13 and χ ≥ Δ, then ω ≥ Δ−3. For a graph G, let H(G) denote the subgraph of G induced by vertices of degree Δ. We also show that if χ ≥ Δ, then ω ≥ Δ or ω(H(G)) ≥ Δ − 5. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 29
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 117002438
- Full Text :
- https://doi.org/10.1137/130929515