IEICE TRANSACTIONS on Information
A Note on Harmonious Coloring of Caterpillars
Summary :
The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.12 pp.2199-2206
- Publication Date
- 2015/12/01
- Publicized
- 2015/08/28
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015EDP7113
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Asahi TAKAOKA
Tokyo Institute of Technology
Shingo OKUMA
Tokyo Institute of Technology
Satoshi TAYU
Tokyo Institute of Technology
Shuichi UENO
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Asahi TAKAOKA, Shingo OKUMA, Satoshi TAYU, Shuichi UENO, "A Note on Harmonious Coloring of Caterpillars" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 12, pp. 2199-2206, December 2015, doi: 10.1587/transinf.2015EDP7113.
Abstract: The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015EDP7113/_p
Copy
@ARTICLE{e98-d_12_2199,
author={Asahi TAKAOKA, Shingo OKUMA, Satoshi TAYU, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on Harmonious Coloring of Caterpillars},
year={2015},
volume={E98-D},
number={12},
pages={2199-2206},
abstract={The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.},
keywords={},
doi={10.1587/transinf.2015EDP7113},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - A Note on Harmonious Coloring of Caterpillars
T2 - IEICE TRANSACTIONS on Information
SP - 2199
EP - 2206
AU - Asahi TAKAOKA
AU - Shingo OKUMA
AU - Satoshi TAYU
AU - Shuichi UENO
PY - 2015
DO - 10.1587/transinf.2015EDP7113
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2015
AB - The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.
ER -
English
