A Note on Harmonious Coloring of Caterpillars
| Autor: | Asahi Takaoka, Shingo Okuma, Satoshi Tayu, Shuichi Ueno |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Combinatorics
Physics::Popular Physics Pathwidth Computer Science::Discrete Mathematics Artificial Intelligence Chromatic scale Electrical and Electronic Engineering harmonious chromatic number Mathematics List coloring Discrete mathematics Mathematics::Combinatorics pathwidth Physics::Physics Education caterpillars Complete coloring Brooks' theorem Edge coloring Computer Science::Sound Hardware and Architecture harmonious coloring Computer Vision and Pattern Recognition Fractional coloring Harmonious coloring Eulerian trail Software |
| Zdroj: | IEICE Transactions on Information and Systems. :2199-2206 |
| ISSN: | 1745-1361 0916-8532 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|