Authors:
S. Kerdjoudj, A.V. Kostochka, A. Raspaud
Title:
List star edge coloring of subcubic graphs
Source:
Discussiones Mathematicae Graph Theory
Received 16.09.2015, Revised 11.05.2017, Accepted 11.05.2017, doi: 10.7151/dmgt.2037

Abstract:
A star edge-coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, chst'(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph G is less than
7
3
(respectively,
5
2
)
, then ch'st(G)≤ 5 (respectively, ch'st(G)≤ 6).
Keywords:
graph coloring, edge coloring, star coloring, planar graphs

Links:
PDF