Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E87-ANo.5pp.1243-1250 Publication Date: 2004/05/01 Online ISSN: DOI: Print ISSN: 0916-8508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: H-coloring, cycles of odd order, complement graphs, NP-completeness,
Full Text: PDF(593.7KB)>>
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.