The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O problema de coloração é um conhecido problema de otimização combinatória de grafos. Este artigo considera Problemas de coloração H, que são problemas de coloração com restrições tais que alguns pares de cores não podem ser usados para vértices adjacentes. A restrição de cores adjacentes pode ser representada por um gráfico H, ou seja, cada vértice representa uma cor e cada aresta significa que as duas cores correspondentes aos dois vértices finais podem ser usadas para vértices adjacentes. Especialmente, H-problema de colorir com um gráfico completo H de ordem k é equivalente ao tradicional k-problema de coloração. Este artigo apresenta condições suficientes para que H-o problema de coloração pode ser reduzido a um H
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Akihiro UEJIMA, Hiro ITO, "On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1026-1030, May 2002, doi: .
Abstract: 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
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1026/_p
Copiar
@ARTICLE{e85-a_5_1026,
author={Akihiro UEJIMA, Hiro ITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs},
year={2002},
volume={E85-A},
number={5},
pages={1026-1030},
abstract={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
keywords={},
doi={},
ISSN={},
month={May},}
Copiar
TY - JOUR
TI - On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1026
EP - 1030
AU - Akihiro UEJIMA
AU - Hiro ITO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - 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
ER -