Cranston–Rabern conjecture on maximum-degree cliques

Let GG be a graph. Write Δ\Delta for its maximum degree, ω\omega for its clique number, and χ\chi for its chromatic number. Let H(G)\mathcal{H}(G) be the subgraph induced by the vertices of degree Δ\Delta. Cranston–Rabern conjecture. If χΔ\chi\ge\Delta, then

ωΔorω(H(G))Δ4.\omega\ge\Delta\quad\text{or}\quad\omega(\mathcal{H}(G))\ge\Delta-4.

The conjecture strengthens the paper’s main theorem by requiring a larger clique among the maximum-degree vertices. It is proved for Δ=6\Delta=6 and Δ=7\Delta=7, and for Δ=3k+1\Delta=3k+1 with k3k\ge3; the stated bound is expected to be tight because of the graph O5O_5.

Sources & referencesView supporting material

Primary source

Daniel W. Cranston and Landon Rabern, “Graphs with χ=Δ have big cliques”, arXiv:1305.3526 (2015).

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.