Paper Info
Title
2-subcoloring is NP-complete for planar comparability graphs.
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 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.
Year
DOI
Venue
2017
10.1016/j.ipl.2017.08.004
Information Processing Letters
Keywords
DocType
Volume
Computational complexity,Graph coloring,NP-completeness
Journal
128
ISSN
Citations 
PageRank 
0020-0190
0
0.34
References 
Authors
2
1
Name
Order
Citations
PageRank
Pascal Ochem125836.91