2-subcoloring is NP-complete for planar comparability graphs

DOI10.1016/J.IPL.2017.08.004MaRDI QIDQ2404616zbMATH OpenOpenAlexWikidataFDO

Authors Pascal Ochem

Publication date 19 September 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.01283

zbMATH Keywords

computational complexitygraph coloringNP-completeness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring is also NP-complete for planar comparability graphs with maximum degree 4.

Recommendations

• scientific article; zbMATH DE number 2044932
• scientific article; zbMATH DE number 1953083
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• More about subcolorings
• Graph Subcolorings: Complexity and Algorithms

Cites work

• Graph Subcolorings: Complexity and Algorithms
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• More about subcolorings
• Near-colorings: non-colorable graphs and NP-completeness
• On star and caterpillar arboricity
• Subcolorings and the subchromatic number of a graph

Cited in

(5)

• Subcolorings and the subchromatic number of a graph
• scientific article; zbMATH DE number 1953083 (Why is no real title available?)
• Graph Subcolorings: Complexity and Algorithms
• scientific article; zbMATH DE number 7589530 (Why is no real title available?)
• Subcoloring of (unit) disk graphs

This page was built for publication: 2-subcoloring is NP-complete for planar comparability graphs

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