Revised square-graph chromatic-choosability conjecture

About 4 years old · traced to

Let GG be a square graph, meaning a graph of the form H2H^2 for some graph HH, and let Δ(G)\Delta(G) denote its maximum degree. Write χ\chi for chromatic number and χℓ\chi_\ell for list chromatic number. Revised square-graph conjecture. Every square graph GG satisfying

χ(G)≥12Δ(G)+1\chi(G)\geq \frac{1}{2}\Delta(G)+1

is chromatic-choosable, that is, satisfies χℓ(G)=χ(G)\chi_\ell(G)=\chi(G). The source proposes this as a revision after its examples violate the corresponding property; its resolution status is not supplied.

References

Primary source

Morteza Hasanvand, “The List Square Coloring Conjecture fails for bipartite planar graphs and their line graphs”, arXiv:2211.00622 (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.