A coloring problem with restrictions of adjacent colors

The coloring problem is a well-known problem of graphs. This paper considers a new coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, called coloring problem with restrictions of adjacent colors. The restriction of adjacent colors can be represented by a graph H called a restriction graph, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices of the edge cannot be used for adjacent vertices. This paper shows some properties of the new coloring problem. It also presents a necessary and sufficient condition such that a restriction graph H cannot be replaced with a more simple graph, when H is a cactus with no 3-cycle.