arXiv
Open Access
2017
2-subcoloring is NP-complete for planar comparability graphs
Pascal Ochem
Abstrak
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.
Topik & Kata Kunci
Penulis (1)
P
Pascal Ochem
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2017
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓