Abstract
Very few NP-complete problems on unlabelled graphs are known to stay NP-complete when restricted to cographs or interval graphs. In this note we prove that the Achromatic Number problem is NP-complete when restricted to connected graphs that are simultaneously a cograph and an interval graph.
| Original language | English |
|---|---|
| Pages (from-to) | 135-138 |
| Number of pages | 4 |
| Journal | Information Processing Letters |
| Volume | 31 |
| Issue number | 3 |
| Publication status | Published - 8 May 1989 |
| Externally published | Yes |
Keywords
- cographs
- interval graphs
- NP-completeness