The complexity of G-free colourability

✍ Scribed by Demetrios Achlioptas

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 758 KB
• Volume: 165-166
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)84217-3

✦ Synopsis

The problem of determining if a graph is 2-colourable (i.e., bipartite) has long been known to have a simple polynomial time algorithm. Being 2-colourable is equivalent to having a bipartition of the vertex set where each cell is &-free. We extend this notion to determining if there exists a bipartition where each cell is G-free for some fixed graph G. One might expect that for some graphs other than K2, K2 there also exist polynomial time algorithms. Rather surprisingly WC show that for UZ~ graph G on more than two vertices the problem is NP-complete.