Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

List coloring C3-free planar graphs with a sparse matching of restricted lists

  • Stephen G. Hartke
  • Yupei Li
  • Joseph Pappe
  • Fares Soufan
  • Lin Tian
  • Zimu Xiang
Open at sourcePDFDOICite

Abstract

A graph G is k-choosable if it has a proper coloring for every k-list assignment. While every C3-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if G is a C3-free planar graph and X ⊆ V(G) induces a bipartite subgraph, then G has a proper L-coloring whenever |L(x)| = 3 for x ∈ X and |L(v)| = 4 for v ∈ V(G) ∖ X. As evidence, they proved the conjecture when X is an independent set. We provide further evidence by proving the conjecture when the induced subgraph G[X] is an induced sparse matching. This is the first result supporting the conjecture in which the set X receiving smaller lists may induce a subgraph with edges.

Related

  1. Bounds for B-coloring planar and outerplanar graphs
    Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
    Discrete MathematicsPeer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
  2. Coloring sparse random Cayley graphs
    Nathan Tung
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
    Enqiang Zhu, Yangyang Zhou, Jin Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
    James Alexander Schreib
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Bounds for B-coloring planar and outerplanar graphs
    Ryan R. Martin, Miklós Ruszinkó, Gábor N. Sárközy
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hartke2026list,
  title = {{List coloring $C_3$-free planar graphs with a sparse matching of restricted lists}},
  author = {Stephen G. Hartke and Yupei Li and Joseph Pappe and Fares Soufan and Lin Tian and Zimu Xiang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.00280},
  eprint = {2609.00280},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.00280},
}
RIS
TY  - UNPB
TI  - List coloring C_3-free planar graphs with a sparse matching of restricted lists
AU  - Stephen G. Hartke
AU  - Yupei Li
AU  - Joseph Pappe
AU  - Fares Soufan
AU  - Lin Tian
AU  - Zimu Xiang
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.00280
UR  - https://arxiv.org/abs/2609.00280
AB  - A graph G is k-choosable if it has a proper coloring for every k-list assignment. While every C_3-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if G is a C_3-free planar graph and X ⊆ V(G) induces a bipartite subgraph, then G has a proper L-coloring whenever |L(x)| = 3 for x ∈ X and |L(v)| = 4 for v ∈ V(G) ∖ X. As evidence, they proved the conjecture when X is an independent set. We provide further evidence by proving the conjecture when the induced subgraph G[X] is an induced sparse matching. This is the first result supporting the conjecture in which the set X receiving smaller lists may induce a subgraph with edges.
ER  -