List star edge coloring of k-degenerate graphs

• Published in: Discrete mathematics 2019-06, Vol.342 (6), p.1838-1848
• Main Authors: Han, Miaomiao, Li, Jiaao, Luo, Rong, Miao, Zhengke
• Format: Article
• Language: English
• Subjects: [formula omitted]-degenerate graph; List star edge coloring; Star edge coloring; Tree
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2019.02.018

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.