{"ID":2824465,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23680","arxiv_id":"2512.23680","title":"Coloring Hardness on Low Twin-Width Graphs","abstract":"As the class $\\mathcal T_4$ of graphs of twin-width at most 4 contains every finite subgraph of the infinite grid and every graph obtained by subdividing each edge of an $n$-vertex graph at least $2 \\log n$ times, most NP-hard graph problems, like Max Independent Set, Dominating Set, Hamiltonian Cycle, remain so on $\\mathcal T_4$. However, Min Coloring and k-Coloring are easy on both families because they are 2-colorable and 3-colorable, respectively. We show that Min Coloring is NP-hard on the class $\\mathcal T_3$ of graphs of twin-width at most 3. This is the first hardness result on $\\mathcal T_3$ for a problem that is easy on cographs (twin-width 0), on trees (whose twin-width is at most 2), and on unit circular-arc graphs (whose twin-width is at most 3). We also show that for every $k \\geqslant 3$, k-Coloring is NP-hard on $\\mathcal T_4$. We finally make two observations: (1) there are currently very few problems known to be in P on $\\mathcal T_d$ (graphs of twin-width at most $d$) and NP-hard on $\\mathcal T_{d+1}$ for some nonnegative integer $d$, and (2) unlike $\\mathcal T_4$, which contains every graph as an induced minor, the class $\\mathcal T_3$ excludes a fixed planar graph as an induced minor; thus it may be viewed as a special case (or potential counterexample) for conjectures about classes excluding a (planar) induced minor. These observations are accompanied by several open questions.","short_abstract":"As the class $\\mathcal T_4$ of graphs of twin-width at most 4 contains every finite subgraph of the infinite grid and every graph obtained by subdividing each edge of an $n$-vertex graph at least $2 \\log n$ times, most NP-hard graph problems, like Max Independent Set, Dominating Set, Hamiltonian Cycle, remain so on $\\m...","url_abs":"https://arxiv.org/abs/2512.23680","url_pdf":"https://arxiv.org/pdf/2512.23680v2","authors":"[\"Édouard Bonnet\"]","published":"2025-12-29T18:36:19Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\",\"math.CO\"]","methods":"[\"LoRA\"]","has_code":false}