2011/02/04 by Landon Rabern, Rabern, Landon
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1102.1021
openalex publication_date 2011/02/04 · arxiv created 2011/08/08 · arxiv updated 2011/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that χ(G) ≤ max ω(G), Δ2(G), (5/6)(Δ(G) + 1) for every graph G with Δ(G) ≥ 3. Here Δ2 is the parameter introduced by Stacho that gives the largest degree that a vertex v can have subject to the condition that v is adjacent to a vertex whose degree is at least as large as its own. This upper bound generalizes both Brooks' Theorem and the Ore-degree version of Brooks' Theorem.