← All problems

Borodin–Kostochka conjecture

19 years old · traced to

All graphs considered are finite, simple, and undirected. For a graph GG, let χ(G)\chi(G) denote its chromatic number, ω(G)\omega(G) its clique number, and Δ(G)\Delta(G) its maximum degree. Borodin–Kostochka conjecture. If

Δ(G)≥9andω(G)≤Δ(G)−1,\Delta(G)\geq 9\quad\text{and}\quad \omega(G)\leq \Delta(G)-1,

then

χ(G)≤Δ(G)−1.\chi(G)\leq \Delta(G)-1.

This conjecture asks for a strengthening of Brooks' theorem when the maximum degree is at least 99 and the clique number is strictly smaller than the maximum degree. It remains open in the supplied source context; the paper studies the conjecture for (P6,C4)(P_6,C_4)-free graphs.

References

16 papers in this index state this conjecture (2007–2026). The statement above is taken from the most recent of them; the others are arXiv:2603.14427, arXiv:2507.10266, arXiv:2408.12693, arXiv:2405.18455, arXiv:2311.08772, arXiv:2310.07214, arXiv:2306.12062, arXiv:2006.02015, arXiv:1708.07369, arXiv:1508.03574, arXiv:1403.0479, arXiv:1311.1251, and 3 more.

Source: Uttam K. Gupta, Dinabandhu Pradhan and Rashmi Rekha Swain, “Coloring (P_6,C_4)-free graphs with Δ- 1 colors”, arXiv:2607.12367 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.