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 …

Coloring Claw-Free Graphs with $\Delta-1$ Colors Page 1 Copyright © by SIAM. Unauthorized
reproduction of this article is prohibited. SIAM J. DISCRETE MATH. c 2013 Society for Industrial …

Brooks' Theorem states that the chromatic number χ (G) of a graph G is at most its maximum
degree Δ (G) when Δ (G)≥ 3 and its clique number ω (G) is at most Δ (G). Vizing …

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 …

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 …

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 χ≥Δ …

Let K p be a complete graph of order p≥ 2. AK p-free k-coloring of a graph H is a partition of
V (H) into V 1, V 2…, V k such that H [V i] does not contain K p for each i≤ k. In 1977 Borodin …

Brooks' theorem states that for a graph G, if Δ (G)≥ 3 and ω (G)≤ Δ (G), then χ (G)≤ Δ (G).
In this paper, we show that this chromatic bound can be further strengthened on (P 6, C 4, H) …

It is shown that any graph with maximum degree Δ in which the average degree of the
induced subgraph on the set of all neighbors of each vertex exceeds is either‐colorable or …

Brooks' Theorem from 1941 is a cornerstone in graph theory. Until then graph coloring
theory was centered around planar graphs and the four color problem. Brooks' Theorem was …