2009/07/21 by Landon Rabern, Rabern, Landon · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.0907.3705
Added simple proof of Kostochka's lemma.
openalex publication_date 2009/07/21 · arxiv created 2010/03/12 · arxiv updated 2010/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that every graph G for which ω(G) ≥ 3/4(Δ(G) + 1), has an independent set I such that ω(G - I) < ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies ω(G) < 3/4(Δ(G) + 1) and hence also χ(G) > \lceil 7/6ω(G) \rceil. We also prove that if for every induced subgraph H of G we have χ(H) ≤ max\lceil 7/6ω(H) \rceil, \lceil (ω(H) + Δ(H) + 1)/(2)\rceil, then we also have χ(G) ≤ \lceil (ω(G) + Δ(G) + 1)/(2)\rceil. This gives a generic proof of the upper bound for line graphs of multigraphs proved by King et al.