Skip to main content
added 507 characters in body
Source Link

The example given by Fedor Petrov is well-known and so is the generalization mentioned by Peter Heinig. Another way to view it is as the line graph of a 5-cycle with all tripled edges. The first appearance i know of was in the 1970s, used by Paul Catlin in his counterexample to the Hajos conjecture https://doi.org/10.1016/0095-8956(79)90062-5

The example with $\chi=\Delta=8$ and $\omega=6$ is also the only known (connected) counterexample to the Borodin-Kostochka conjecture for $\Delta=8$.

The more general examples prove tightness of a conjecture on the chromatic number of vertex transitive graphs Cranston and i made: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1

That conjecture is that vertex transitive graphs with $\chi > \omega$ have $\chi \le (5\Delta + 8) / 6$. This is proved fractionally and the full conjecture follows from Reed's conjecture combined with the strong coloring conjecture. The conjecture is open even for Cayley graphs.

Another related conjecture that the example shows tightness for given by Cranston and i in http://epubs.siam.org/doi/abs/10.1137/130929515 is that graphs with $\omega < \Delta - 3$ have $\chi < \Delta$. We prove this for $\Delta \ge 13$. The remaining open cases are $\Delta = 6,8,9,11,12$.

Another way to say that is that the OP's question is open in the cases:

(6,6,3), (8,8,5), (9,9,6), (11,11,8), (12,12,9).

The example given by Fedor Petrov is well-known and so is the generalization mentioned by Peter Heinig. The first appearance i know of was in the 1970s, used by Paul Catlin in his counterexample to the Hajos conjecture https://doi.org/10.1016/0095-8956(79)90062-5

The example with $\chi=\Delta=8$ and $\omega=6$ is also the only known (connected) counterexample to the Borodin-Kostochka conjecture for $\Delta=8$.

The more general examples prove tightness of a conjecture on the chromatic number of vertex transitive graphs Cranston and i made: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1

That conjecture is that vertex transitive graphs with $\chi > \omega$ have $\chi \le (5\Delta + 8) / 6$. This is proved fractionally and the full conjecture follows from Reed's conjecture combined with the strong coloring conjecture. The conjecture is open even for Cayley graphs.

The example given by Fedor Petrov is well-known and so is the generalization mentioned by Peter Heinig. Another way to view it is as the line graph of a 5-cycle with all tripled edges. The first appearance i know of was in the 1970s, used by Paul Catlin in his counterexample to the Hajos conjecture https://doi.org/10.1016/0095-8956(79)90062-5

The example with $\chi=\Delta=8$ and $\omega=6$ is also the only known (connected) counterexample to the Borodin-Kostochka conjecture for $\Delta=8$.

The more general examples prove tightness of a conjecture on the chromatic number of vertex transitive graphs Cranston and i made: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1

That conjecture is that vertex transitive graphs with $\chi > \omega$ have $\chi \le (5\Delta + 8) / 6$. This is proved fractionally and the full conjecture follows from Reed's conjecture combined with the strong coloring conjecture. The conjecture is open even for Cayley graphs.

Another related conjecture that the example shows tightness for given by Cranston and i in http://epubs.siam.org/doi/abs/10.1137/130929515 is that graphs with $\omega < \Delta - 3$ have $\chi < \Delta$. We prove this for $\Delta \ge 13$. The remaining open cases are $\Delta = 6,8,9,11,12$.

Another way to say that is that the OP's question is open in the cases:

(6,6,3), (8,8,5), (9,9,6), (11,11,8), (12,12,9).

Source Link

The example given by Fedor Petrov is well-known and so is the generalization mentioned by Peter Heinig. The first appearance i know of was in the 1970s, used by Paul Catlin in his counterexample to the Hajos conjecture https://doi.org/10.1016/0095-8956(79)90062-5

The example with $\chi=\Delta=8$ and $\omega=6$ is also the only known (connected) counterexample to the Borodin-Kostochka conjecture for $\Delta=8$.

The more general examples prove tightness of a conjecture on the chromatic number of vertex transitive graphs Cranston and i made: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1

That conjecture is that vertex transitive graphs with $\chi > \omega$ have $\chi \le (5\Delta + 8) / 6$. This is proved fractionally and the full conjecture follows from Reed's conjecture combined with the strong coloring conjecture. The conjecture is open even for Cayley graphs.