On the Structure of Potential Counterexamples to the Borodin-Kostochka Conjecture
Time: 14:00 -- Location: LRI, 445
summary: The Borodin-Kostochka conjecture, a long-standing problem in graph theory, asserts that every graph \(G\)
with maximum degree \(\Delta \geq 9\) satisfies \(\chi(G) \leq max \{\Delta - 1, \omega(G)\}\) where \(\chi(G)\) and \(\omega(G)\)
are respectively the chromatic number and the clique number of \(G\). While the conjecture remains unresolved,
significant progress has been made in understanding the structure of potential counterexamples. Our approach relies,
among other things on a result concerning the strong chromatic number of graphs, which offers new insights into
the structural properties of potential counterexamples.
This talk will outline our findings and place them in the context of ongoing work on the conjecture.
While the results do not solve the conjecture, they contribute to a deeper understanding of the problem
and the nature of its potential counterexamples.
This is joint work with Marthe Bonamy, Lucas De Meyer and J\k{e}drzej Hodor