On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H´-coloring problem, where H´ is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n &prne; 5.
社団法人電子情報通信学会の論文
2002-05-01