Premium
A Coloring Problem With Restrictions of Adjacent Colors
Author(s) -
Akihiro Uejima,
Hiro Ito,
Hideyuki Uehara,
Mitsuo Yokoyama
Publication year - 2002
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00349
Subject(s) - edge coloring , combinatorics , graph coloring , fractional coloring , complete coloring , greedy coloring , mathematics , list coloring , vertex (graph theory) , brooks' theorem , graph , graph power , line graph
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.