Cranston–Rabern equivalent form of the Borodin–Kostochka conjecture

Let GG be a simple graph. Write χ=χ(G)\chi=\chi(G) for its chromatic number and Δ=Δ(G)\Delta=\Delta(G) for its maximum degree. For graphs G1G_1 and G2G_2, let G1G2G_1\lor G_2 denote their join, and let EtE_t be the edgeless graph on tt vertices. Cranston–Rabern equivalent conjecture. Every graph with χ=Δ=9\chi=\Delta=9 contains K3E6K_3\lor E_6 as a subgraph. This formulation is stated to be completely equivalent to the Borodin–Kostochka conjecture and focuses the problem on the minimum relevant maximum degree, 99; it remains open.

Sources & referencesView supporting material

Primary source

Rachel Galindo and Jessica McDonald, “On graphs with chromatic number and maximum degree both equal to nine”, arXiv:2408.12693 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.