2022/07/25 by Jeffrey A. Mudrock, Mudrock, Jeffrey A.
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.11868
openalex publication_date 2022/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
List packing is a notion that was introduced in 2021 (by Cambie et al.). The list packing number of a graph G, denoted χℓ^*(G), is the least k such that for any list assignment L that assigns k colors to each vertex of G, there is a set of k proper L-colorings of G, \f1, …, fk \, with the property fi(v) ≠ fj(v) whenever 1 ≤ i < j ≤ k and v ∈ V(G). We present a short proof that for any graph G, χℓ^*(G) ≤ |V(G)|. Interestingly, our proof makes use of Galvin's celebrated result that the list chromatic number of the line graph of any bipartite multigraph equals its chromatic number.