jeu. 05 décembre 2024 -- Jonathan Narboni (LaBRI)

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 ...