Brooks' theorem and beyond
DW Cranston, L Rabern - Journal of Graph Theory, 2015 - Wiley Online Library
We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and
extensions of each. The proofs illustrate some of the major techniques in graph coloring …
extensions of each. The proofs illustrate some of the major techniques in graph coloring …
Borodin–Kostochka's conjecture on -free graphs
Brooks' theorem states that for a graph G, if\varDelta (G) ≥ 3 Δ (G)≥ 3, then χ (G) ≤\max
{\varDelta (G), ω (G)\} χ (G)≤ max Δ (G), ω (G). Borodin and Kostochka conjectured a result …
{\varDelta (G), ω (G)\} χ (G)≤ max Δ (G), ω (G). Borodin and Kostochka conjectured a result …
Coloring (P 5, gem) (P_5,gem)‐free graphs with Δ− 1 Δ-1 colors
DW Cranston, H Lafayette, L Rabern - Journal of Graph Theory, 2022 - Wiley Online Library
Abstract The Borodin–Kostochka Conjecture states that for a graph GG, if Δ (G)≥ 9 Δ(G)≥9
and ω (G)≤ Δ (G)− 1 ω(G)≤Δ(G)-1, then χ (G)≤ Δ (G)− 1 χ(G)≤Δ(G)-1. We prove the …
and ω (G)≤ Δ (G)− 1 ω(G)≤Δ(G)-1, then χ (G)≤ Δ (G)− 1 χ(G)≤Δ(G)-1. We prove the …
Coloring {P2∪ P3, house}-free graphs with Δ− 1 colors
R Chen, K Lan, Y Zhou - Discrete Applied Mathematics, 2024 - Elsevier
A house is the graph that consists of an induced 4-vertex cycle and a single vertex with
precisely two adjacent neighbors on the cycle. The Borodin–Kostochka Conjecture states …
precisely two adjacent neighbors on the cycle. The Borodin–Kostochka Conjecture states …
Borodin–Kostochka Conjecture Holds for Odd-Hole-Free Graphs
R Chen, K Lan, X Lin, Y Zhou - Graphs and Combinatorics, 2024 - Springer
Borodin–Kostochka Conjecture Holds for Odd-Hole-Free Graphs | Graphs and Combinatorics
Skip to main content SpringerLink Account Menu Find a journal Publish with us Track your …
Skip to main content SpringerLink Account Menu Find a journal Publish with us Track your …
χ-boundedness and related problems on graphs without long induced paths: A survey
A Char, T Karthick - Discrete Applied Mathematics, 2025 - Elsevier
Given a hereditary class of graphs G, a function f: N→ N such that f (1)= 1 and f (x)≥ x, for all
x∈ N is a χ-binding function for G if χ (G)≤ f (ω (G)), for each G∈ G. The class G is called χ …
x∈ N is a χ-binding function for G if χ (G)≤ f (ω (G)), for each G∈ G. The class G is called χ …
Painting Squares in Shades
DW Cranston, L Rabern - arXiv preprint arXiv:1311.1251, 2013 - arxiv.org
Cranston and Kim conjecture that if $ G $ is a connected graph with maximum degree
$\Delta $ and $ G $ is not a Moore Graph, then $\chi_l (G^ 2)\le\Delta^ 2-1$; here $\chi_l $ is …
$\Delta $ and $ G $ is not a Moore Graph, then $\chi_l (G^ 2)\le\Delta^ 2-1$; here $\chi_l $ is …
Borodin-Kostochka conjecture for a class of P_6-free graphs
D Wu, R Wu - arXiv preprint arXiv:2306.12062, 2023 - arxiv.org
Borodin and Kostochka conjectured that every graph $ G $ with $\Delta\ge9 $ satisfies
$\chi\le $ max $\{\omega,\Delta-1\} $. This conjecture is still open for general graphs. In this …
$\chi\le $ max $\{\omega,\Delta-1\} $. This conjecture is still open for general graphs. In this …
A Note on -Critical Graphs
P Haxell, R Naserasr - Graphs and Combinatorics, 2023 - Springer
A k-critical graph is ak-chromatic graph whose proper subgraphs are all (k-1)-colourable. An
old open problem due to Borodin and Kostochka asserts that for k≥ 9, no k-critical graph G …
old open problem due to Borodin and Kostochka asserts that for k≥ 9, no k-critical graph G …
Graphs with Have Big Cliques
DW Cranston, L Rabern - SIAM Journal on Discrete Mathematics, 2015 - SIAM
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 χ≥Δ …
Kostochka conjectured that if Δ≥9 and χ≥Δ, then ω≥Δ. We show that if Δ≥13 and χ≥Δ …