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 C_(2p+1) of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maxima) planar graphs are C_(2p+1)-colorable if and only if they are p-colorable (p≧2), (2) C_7-coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many C_7-colorable but non-3-colorable planar graphs.
展开▼
