Griggs–Yeh L(2,1)-labeling conjecture

Let GG be a graph with maximum degree Δ\Delta, and let λ2,1(G)\lambda^{2,1}(G) be the minimum span of an L(2,1)L(2,1)-labeling, in which vertices at distance one receive labels differing by at least 22 and vertices at distance two receive distinct labels. Griggs–Yeh conjecture.

λ2,1(G)Δ2.\lambda^{2,1}(G)\le\Delta^2.

This conjecture is the labeling analogue of quadratic coloring bounds for graph squares; the survey does not state a general resolution.

Sources & referencesView supporting material

Primary source

Daniel W. Cranston, “Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)”, arXiv:2210.05915 (2026).

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.