On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs

Akihiro UEJIMA  Hiro ITO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.1026-1030
Publication Date: 2002/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
H-coloring,  bipartite graphs,  chordal graph,  complement graphs,  perfect graphs,  

Full Text: PDF(504.4KB)>>
Buy this Article



Summary: 
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 5.