Sufficiency of Hall's Condition for Graphic List Coloring
Abstract
For finite simple graphs G,H on a common vertex set V, we say that H is G-colorable if H admits a proper list coloring with list assignment L(v)=NG(v) for all v∈ V. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call \emph{graphic list coloring}, has connections to several classical topics, including systems of distinct representatives and graph factorizations. In this paper, we investigate when a necessary Hall-type condition, introduced by Hilton and Johnson in 1990, is also sufficient for H to be G-colorable. We characterize all graphs H that are G-colorable whenever the pair (H,G) satisfies Hall's condition, answering a question raised by Johnson. We then consider the dual problem of characterizing graphs G such that, whenever (H,G) satisfies Hall's condition, H is G-colorable. In this vein, we obtain complete results for several families of graphs, such as forests, complete multipartite graphs, and grid graphs.
Related
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- The List Edge-Coloring Conjecture for New Infinite Families
- Restricting Odd Antiholes in Critical Graphs via List Coloring
- Counterexamples to Relaxed Multiplication in List Coloring
BibTeX
@misc{chalise2026sufficiency,
title = {{Sufficiency of Hall's Condition for Graphic List Coloring}},
author = {Parikshit Chalise},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01889},
eprint = {2609.01889},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01889},
}
RIS
TY - UNPB
TI - Sufficiency of Hall's Condition for Graphic List Coloring
AU - Parikshit Chalise
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01889
UR - https://arxiv.org/abs/2609.01889
AB - For finite simple graphs G,H on a common vertex set V, we say that H is G-colorable if H admits a proper list coloring with list assignment L(v)=N_G(v) for all v∈ V. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call \emph{graphic list coloring}, has connections to several classical topics, including systems of distinct representatives and graph factorizations. In this paper, we investigate when a necessary Hall-type condition, introduced by Hilton and Johnson in 1990, is also sufficient for H to be G-colorable. We characterize all graphs H that are G-colorable whenever the pair (H,G) satisfies Hall's condition, answering a question raised by Johnson. We then consider the dual problem of characterizing graphs G such that, whenever (H,G) satisfies Hall's condition, H is G-colorable. In this vein, we obtain complete results for several families of graphs, such as forests, complete multipartite graphs, and grid graphs.
ER -