| Presentation | 2014-11-20 Harmonious Coloring of Caterpillars Asahi TAKAOKA, Shingo OKUMA, Satoshi TAYU, Shuichi UENO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The harmonious coloring of a 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 of determining 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 known as caterpillars. This paper shows the harmonious chromatic number of shooting stars and comets, which are ones of the simplest kinds of caterpillar. We also show the upper bound of harmonious chromatic number of 3-regular caterpillars. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Caterpillars / Eulerian trail / Harmonious coloring / Harmonious chromatic number |
| Paper # | CAS2014-93,MSS2014-57 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2014/11/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Harmonious Coloring of Caterpillars |
| Sub Title (in English) | |
| Keyword(1) | Caterpillars |
| Keyword(2) | Eulerian trail |
| Keyword(3) | Harmonious coloring |
| Keyword(4) | Harmonious chromatic number |
| 1st Author's Name | Asahi TAKAOKA |
| 1st Author's Affiliation | Department of Communications and Computer Engineering, Tokyo Institute of Technology Tokyo() |
| 2nd Author's Name | Shingo OKUMA |
| 2nd Author's Affiliation | Department of Communications and Computer Engineering, Tokyo Institute of Technology Tokyo |
| 3rd Author's Name | Satoshi TAYU |
| 3rd Author's Affiliation | Department of Communications and Computer Engineering, Tokyo Institute of Technology Tokyo |
| 4th Author's Name | Shuichi UENO |
| 4th Author's Affiliation | Department of Communications and Computer Engineering, Tokyo Institute of Technology Tokyo |
| Date | 2014-11-20 |
| Paper # | CAS2014-93,MSS2014-57 |
| Volume (vol) | vol.114 |
| Number (no) | 313 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |