# The Borodin-Kostochka Conjecture

 Importance: Medium ✭✭
 Author(s): Borodin, Oleg V. Kostochka, Alexandr V.
 Subject: Graph Theory
 Keywords:
 Posted by: Andrew King on: September 10th, 2012
Conjecture   Every graph with maximum degree has chromatic number at most .

The Borodin-Kostochka conjecture proposes that for any graph with maximum degree and clique number , is colourable so long as is sufficiently large (specifically, ). The requirement that is necessary, as one can see by looking at the strong product of and .

Reed [R] proved that there exists a for which the conjecture holds whenever . Specifically he proved that , but claims that more careful analysis could reduce to 1000.

The conjecture was recently proven by Cranston and Rabern for claw-free graphs [CR]. In their paper they mention an unpublished strengthening proposed by Borodin and Kostochka, namely that one can replace the chromatic number in the statement of the conjecture with the list chromatic number.

## Bibliography

[BK] O. V. Borodin and A. V. Kostochka. On an upper bound of a graph's chromatic number, depending on the graph's degree and density. JCTB 23 (1977), 247--250.

[CR] D. W. Cranston and L. Rabern. Coloring claw-free graphs with colors, arXiv 1206.1269, 2012.

[R] B. A. Reed. A strengthening of Brooks’ Theorem. J. Comb. Theory Ser. B, 76:136–149, 1999.

* indicates original appearance(s) of problem.