首页 | 官方网站   微博 | 高级检索  
     


List star edge coloring of k-degenerate graphs
Authors:Miaomiao Han  Jiaao Li  Rong Luo  Zhengke Miao
Abstract:A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree Δ is at most ?3Δ2?, which is tight. In this paper, we study the list star edge coloring of k-degenerate graphs. Let chst(G) be the list star chromatic index of G: the minimum s such that for every s-list assignment L for the edges, G has a star edge coloring from L. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. chst(T)?3Δ2? for any tree T with maximum degree Δ. And then by applying some orientation technique we present two upper bounds for list star chromatic index of k-degenerate graphs.
Keywords:Corresponding author    Star edge coloring  List star edge coloring  Tree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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

京公网安备 11010802026262号