arXiv:2611.05423v1 Announce Type: new Abstract: We prove that every finite simple graph $G$ with maximum degree at least $750$ satisfies $\chi(G)\le\max\{\omega(G),\Delta(G)-1\}$. The proof starts with a random partial colouring and completes it on large cliques using a list-colouring condition that remains valid as the rest of the graph is coloured. Disjoint stars provide the required colours. We estimate the number of stars that can be chosen after the clique colours have been exposed, while keeping their endpoint set fixed. A common exponential-moment argument reduces intervals of packing sizes to endpoint comparisons. More detailed neighbourhood estimates handle the remaining vertices. The final probability inequalities are verified by directed rational and interval arithmetic.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page