On the strong chromatic index of cubic Halin graphs
On the strong chromatic index of cubic Halin graphs
复制标题
DOI：
10.1016/j.aml.2011.10.046
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Ko-Wei Lih;Daphne Der-Fen Liu
中科院分区：
文献类型：
--
作者：
Ko-Wei Lih;Daphne Der-Fen Liu
图G的强边着色是对图G的边的颜色分配，使得两个不同的边在一个共同的边或共享一个端点时具有不同的颜色。图G的强着色指数，用sχ’(G)表示，是图G的强边着色所需的最小颜色数。Halin图G是由一棵没有2次顶点的树通过一个循环连接所有叶子构造的平面图。如果一个三次Halin图G不同于两个特定的图ne2和Ne4，那么我们证明了sχ ' (G)≥7。本文解决了在《完全三次Halin图的强色指数》中提出的一个猜想。数学。快报22(2009)754-758。
A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if they are incident to a common edge or share an endpoint. The strong chromatic index of a graph G, denoted by sχ′(G), is the minimum number of colors needed for a strong edge coloring of G. A Halin graph G is a plane graph constructed from a tree without vertices of degree two by connecting all leaves through a cycle. If a cubic Halin graph G is different from two particular graphs Ne2and Ne4, then we prove sχ′(G)⩽7. This solves a conjecture proposed in W.C. Shiu, W.K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett. 22 (2009) 754–758.