2017/02/04 by Pascal Ochem, Ochem, Pascal · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1702.01283
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 P3. 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.