Subcoloring of (unit) disk graphs

DOI10.4230/LIPICS.MFCS.2025.74MaRDI QIDQ7310249zbMATH OpenFDO

Authors Malory Marin, Rémi Watrigant

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.74

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 2-subcoloring is NP-complete for planar comparability graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• scientific article; zbMATH DE number 2044932 (Why is no real title available?)
• scientific article; zbMATH DE number 3307332 (Why is no real title available?)
• Kontaktprobleme der konformen Abbildung.
• More about subcolorings
• Near-colorings: non-colorable graphs and NP-completeness
• On 2-Subcolourings of Chordal Graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Sub-coloring and hypo-coloring interval graphs
• Subcolorings and the subchromatic number of a graph
• The subchromatic number of a graph

This page was built for publication: Subcoloring of (unit) disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310249)