-Coloring Problem

Akihiro UEJIMA  Hiro ITO  Tatsuie TSUKIJI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1243-1250
Publication Date: 2004/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
H-coloring,  cycles of odd order,  complement graphs,  NP-completeness,  

Full Text: PDF(593.7KB)>>
Buy this Article

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.