Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 46 min ago
PreprintCC BY 4.0arXiv

List 3-Coloring in tame classes of graphs in quasipolynomial time

  • Paweł Rzążewski
Open at sourcePDFDOICite

Abstract

A class of graphs 𝒢 is tame if there is a constant c such that every n-vertex graph in 𝒢 has at most nc minimal separators. Many important graph classes are tame, including chordal graphs, permutation graphs, and circle graphs. Several fundamental problems, most notably Max Weight Independent Set, can be solved in polynomial time on every tame class, which explains in a unified way their tractability on all these classes. We show that List 3-Coloring can be solved in quasipolynomial time on every tame class of graphs.

Related

  1. List coloring C3-free planar graphs with a sparse matching of restricted lists
    Stephen G. Hartke, Yupei Li, Joseph Pappe +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Restricting Odd Antiholes in Critical Graphs via List Coloring
    Alireza Fiujlaali, Jessica McDonald
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Dominated Coloring of Some Classes of Perfect and Unicyclic Graphs
    Sneha R, J. Geetha, K. Somasundaram
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Functorial equivalence classes of 2-blocks of tame representation type
    Robert Boltje, Serge Bouc, Deniz Yılmaz
    Tunisian Journal of MathematicsPeer-reviewedLicence not statedFull textCombinatorics & discrete mathematicsHAL
  5. Sufficiency of Hall's Condition for Graphic List Coloring
    Parikshit Chalise
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{rzazewski2026list,
  title = {{List 3-Coloring in tame classes of graphs in quasipolynomial time}},
  author = {Paweł Rzążewski},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41620},
  eprint = {2610.41620},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41620},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - List 3-Coloring in tame classes of graphs in quasipolynomial time
AU  - Paweł Rzążewski
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41620
UR  - https://arxiv.org/abs/2610.41620
AB  - A class of graphs 𝒢 is tame if there is a constant c such that every n-vertex graph in 𝒢 has at most n^c minimal separators. Many important graph classes are tame, including chordal graphs, permutation graphs, and circle graphs. Several fundamental problems, most notably Max Weight Independent Set, can be solved in polynomial time on every tame class, which explains in a unified way their tractability on all these classes. We show that List 3-Coloring can be solved in quasipolynomial time on every tame class of graphs.
ER  -