Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647818 | Discrete Mathematics | 2012 | 8 Pages |
Abstract
A strong edge-coloring of a graph GG is a function that assigns to each edge a color such that two edges within distance two apart must receive different colors. The minimum number of colors used in a strong edge-coloring is the strong chromatic index of GG. Lih and Liu (2011) [14] proved that the strong chromatic index of a cubic Halin graph, other than two special graphs, is 6 or 7. It remains an open problem to determine which of such graphs have strong chromatic index 6. Our article is devoted to this open problem. In particular, we disprove a conjecture of Shiu et al. (2006) [18] that the strong chromatic index of a cubic Halin graph with characteristic tree a caterpillar of odd leaves is 6.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gerard Jennhwa Chang, Daphne Der-Fen Liu,