Kostochka–Kierstead Ore-degree Chen–Lih–Wu conjecture

For a graph GG, define its Ore-degree by

Θ(G):=max{d(x)+d(y):xyE(G)}.\Theta(G):=\max\{d(x)+d(y):xy\in E(G)\}.

A proper coloring is equitable when its color classes differ in size by at most one. Kostochka–Kierstead's Ore-degree conjecture. Let GG be a connected graph with Θ(G)2k\Theta(G)\leq2k and k3k\geq3. If GG is distinct from Kk+1K_{k+1} and from Km,2kmK_{m,2k-m} for odd mm, then GG has an equitable kk-coloring. The source says this conjecture was proved for k=3k=3 and relates it to a stronger equivalent formulation.

Sources & referencesView supporting material

Primary source

H. A. Kierstead, Alexandr Kostochka and Zimu Xiang, “Results and Problems on Equitable Coloring of Graphs”, arXiv:2504.14711 (2025).

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.