Article ID Journal Published Year Pages File Type
4649471 Discrete Mathematics 2009 10 Pages PDF
Abstract

We show that if HH is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar HH-COL is NPNP-complete.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On the complexity of HH-colouring planar graphs
Authors
, ,