Star 5-edge-colorings of subcubic multigraphs |
| |
Authors: | Hui Lei Yongtang Shi Zi-Xia Song Tao Wang |
| |
Affiliation: | 1. Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China;2. Department of Mathematics, University of Central Florida, Orlando, FL32816, USA;3. Institute of Applied Mathematics, Henan University, Kaifeng, 475004, PR China |
| |
Abstract: | The star chromatic index of a mulitigraph , denoted , is the minimum number of colors needed to properly color the edges of such that no path or cycle of length four is bi-colored. A multigraph is star-edge-colorable if . Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than is star list-5-edge-colorable. It is known that a graph with maximum average degree is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than is star 5-edge-colorable. |
| |
Keywords: | Star edge-coloring Subcubic multigraphs Maximum average degree |
本文献已被 ScienceDirect 等数据库收录! |
|