2-subcoloring is NP-complete for planar comparability graphs

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 per...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2017-12, Vol.128, p.46-48
Main Author: Ochem, Pascal
Format: Article
Language:English
Subjects:
Computational complexity
Computer Science
Discrete Mathematics
Graph coloring
NP-completeness
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2017.08.004