C-7-coloring problem
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 (C2p+1) over bar of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are (C2p+1) over bar -colorable if and only if they are p-colorable (p greater than or equal to 2), (2) C-7-coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many (C-7) over bar -colorable but non-3-colorable planar graphs.
h-coloring complement graphs cycles of odd order np-completeness