http://swrc.ontoware.org/ontology#Article
A Note on Harmonious Coloring of Caterpillars
en
caterpillars
Eulerian trail
harmonious coloring
harmonious chromatic number
pathwidth
TAKAOKA Asahi
OKUMA Shingo
TAYU Satoshi
UENO Shuichi
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.
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
E98D
12
2199-2206
2015
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
info:doi/10.1587/transinf.2015EDP7113
548
1745-1361
Copyright © 2015 IEICE
https://search.ieice.org/index.html|IEICE Transactions Online TOP
application/pdf