On (s, t)-relaxed strong edge-coloring of graphs

详细信息    查看全文

• 作者：Dan He ; Wensong Lin
• 关键词：Strong edge ; coloring ; Strong chromatic index ; \((s ; t)\) ; relaxed strong edge ; coloring ; \((s ; t)\) ; relaxed strong chromatic index ; Tree ; Infinite \(\Delta \) ; regular tree
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：609-625
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

In this paper, we introduce a new relaxation of strong edge-coloring. Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is an assignment of k colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by \({\chi '}_{(s,t)}(G)\), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. This paper studies the (s, t)-relaxed strong edge-coloring of graphs, especially trees. For a tree T, the tight upper bounds for \({\chi '}_{(s,0)}(T)\) and \({\chi '}_{(0,t)}(T)\) are given. And the (1, 1)-relaxed strong chromatic index of an infinite regular tree is determined. Further results on \({\chi '}_{(1,0)}(T)\) are also presented.