The Borodin-Kostochka Conjecture

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Andrew King
on: September 10th, 2012

\begin{conjecture} Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

The Borodin-Kostochka conjecture proposes that for any graph $G$ with maximum degree $\Delta$ and clique number $\omega < \Delta$, $G$ is $\Delta-1$ colourable so long as $\Delta$ is sufficiently large (specifically, $\Delta\geq 9$). The requirement that $\Delta \geq 9$ is necessary, as one can see by looking at the strong product of $C_5$ and $K_3$.

Reed [R] proved that there exists a $\Delta_0$ for which the conjecture holds whenever $\Delta \geq \Delta_0$. Specifically he proved that $\Delta_0 \leq 10^{14}$, but claims that more careful analysis could reduce $\Delta_0$ 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.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [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. \arxiv[Coloring claw-free graphs with $\Delta-1$ colors]{1206.1269}, 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.