Title of article :
On the complexity of -colouring planar graphs
Author/Authors :
MacGillivray، نويسنده , , G. and Siggers، نويسنده , , M.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H -COL is N P -complete.
Keywords :
Graph homomorphism , H -colouring , Planar graph , NP-Completeness
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics
