Subdivision of the hierarchy of H-colorable graph classes by circulant graphs

For any integer p ⩾ 2 , p-colorable graphs are C 2 p + 1 ¯ -colorable and C 2 p + 1 ¯ -colorable graphs are p + 1 -colorable, where C 2 p + 1 ¯ is the complement graph of a cycle of order 2 p + 1 . The converse statements are however incorrect. This paper presents that the above inclusion can be subdivided by a subset of circulant graphs H ( n , k ) ( n , k ∈ N , k ⩽ ⌊ n / 2 ⌋ ) . The subdivided hierarchy of inclusion contains the well-known inclusion of C 2 p + 1 -colorable graphs. Moreover, we prove some NP-complete problems for planar H ( n , k ) -colorings, including the C 5 ¯ -coloring.