The List Edge-Coloring Conjecture for New Infinite Families
Abstract
The List Edge-Coloring Conjecture predicts that any graph whose edges can be colored with k colors can also be colored from arbitrary lists of k colors. We prove its stronger online form for two new infinite families, Kp−1 and K2p, where p is an odd prime. For even n, order the vertices of Kn and draw each perfect matching as arcs above them. Count crossings separately within each matching, and let Sn be the number of decompositions into perfect matchings having an even total crossing count minus the number having an odd total. Then Sp−1≡((−2)/p)pmod p, S2p≡−ppmod p2. The two congruences are governed by the same elementary matching sum over Fp, although their proofs use the prime p differently. Their nonzero residues give the conjectured values even in the online game. They also treat the corresponding complete graphs with one perfect matching removed, as well as K2p after deleting some, but not all, of a natural cyclic family of p disjoint perfect matchings.
Related
- Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples
- Infinite Families of Counterexamples to a Conjecture of Liu and Qian and a Refined Inverse Theorem for Restricted Sumsets in ℤp
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- Sufficiency of Hall's Condition for Graphic List Coloring
BibTeX
@misc{jafari2026list,
title = {{The List Edge-Coloring Conjecture for New Infinite Families}},
author = {Amir Jafari},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.22895},
eprint = {2608.22895},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.22895},
}
RIS
TY - UNPB
TI - The List Edge-Coloring Conjecture for New Infinite Families
AU - Amir Jafari
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2608.22895
UR - https://arxiv.org/abs/2608.22895
AB - The List Edge-Coloring Conjecture predicts that any graph whose edges can be colored with k colors can also be colored from arbitrary lists of k colors. We prove its stronger online form for two new infinite families, K_p−1 and K_2p, where p is an odd prime. For even n, order the vertices of K_n and draw each perfect matching as arcs above them. Count crossings separately within each matching, and let S_n be the number of decompositions into perfect matchings having an even total crossing count minus the number having an odd total. Then S_p−1≡((−2)/p)pmod p, S_2p≡−ppmod p^2. The two congruences are governed by the same elementary matching sum over F_p, although their proofs use the prime p differently. Their nonzero residues give the conjectured values even in the online game. They also treat the corresponding complete graphs with one perfect matching removed, as well as K_2p after deleting some, but not all, of a natural cyclic family of p disjoint perfect matchings.
ER -