Strong edge-coloring of 2-degenerate graphs

被引：1

作者：

Yu, Gexin ^{[1
]}

Yu, Rachel ^{[2
]}

机构：

[1] William & Mary, Dept Math, Williamsburg, VA 23185 USA

[2] Jamestown High Sch, Williamsburg, VA 23185 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2023年 / 336卷

关键词：

Strong edge-coloring; 2-Degenerate graph; STRONG CHROMATIC INDEX;

D O I：

10.1016/j.dam.2023.03.028

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A strong edge-coloring of a graph G is an edge-coloring in which every color class is an induced matching, and the strong chromatic index chi(s)' (G) is the minimum number of colors needed in strong edge-colorings of G. A graph is 2-degenerate if every subgraph has minimum degree at most 2. Choi, Kim, Kostochka, and Raspaud (2016) showed chi(s)'(G) <= 5 Delta + 1 if G is a 2-degenerate graph with maximum degree Delta. In this article, we improve it to chi(s)'(G) <= 5 Delta - Delta(1/2-is an element of) + 2 when Delta >= 4(1/(2 is an element of)) for any 0 < is an element of <= 1/2. (c) 2023 Elsevier B.V. All rights reserved.

引用

页码：11 / 14

页数：4

共 16 条

[1] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10 [J].