Proof of the List Coloring Conjecture for line perfect multigraphs

2019/04/14 by Alexey Gordeev, Gordeev, Alexey
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1904.06662

openalex publication_date 2019/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for a line perfect multigraph the chromatic index is equal to the list chromatic index. This is a generalization of Galvin's result on bipartite multigraphs. Soon after the first version was submitted to arxiv, I found out that the same result has already been achieved in an older paper by Peterson and Woodall, by a similar but not entirely the same method.

Citations

• On Representatives of Subsets

Related

• Generalized list colouring of graphs
• A Short Proof that the List Packing Number of any Graph is Well Defined
• List Supermodular Coloring with Shorter Lists
• A list analog of Vizing's Theorem for simple graphs with triangles but\n no other odd cycles
• List colouring of graphs with at most (2-o(1))χ vertices