-Coloring Problem

Akihiro UEJIMA, Hiro ITO, Tatsuie TSUKIJI

Summary :

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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1243-1250
• Publication Date: 2004/05/01
• Type of Manuscript: PAPER
• Category: Graphs and Networks

Authors

Akihiro UEJIMA
Hiro ITO
Tatsuie TSUKIJI

Keyword

H-coloring,  cycles of odd order,  complement graphs,  NP-completeness