首页 | 本学科首页   官方微博 | 高级检索  
     


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 G, denoted χs(G), is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bi-colored. A multigraph G is stark-edge-colorable if χs(G)k. 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 73 is star list-5-edge-colorable. It is known that a graph with maximum average degree 145 is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than 125 is star 5-edge-colorable.
Keywords:Star edge-coloring  Subcubic multigraphs  Maximum average degree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号