Vizing–Gupta–Albertson–Collins–Bollobás–Harris line-graph List Coloring Conjecture

About 4 years old · traced to

Let GG be a graph and let L(G)L(G) be its line graph, whose vertices are the edges of GG, with two vertices adjacent when the corresponding edges share an endpoint. Write χ\chi for chromatic number and χℓ\chi_\ell for list chromatic number. Line-graph List Coloring Conjecture. Every graph GG satisfies

χ(L(G))=χℓ(L(G)).\chi(L(G))=\chi_\ell(L(G)).

The source notes that this conjecture is proved for bipartite graphs, while its general status is not resolved in the supplied material.

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.