List Strong Edge-Colorings of Sparse Graphs

A strong edge-coloring of a graph G = (V, E) is a partition of its edge set E into induced matchings. In this paper, wewill study the list version of strong edge-colorings of several classes of sparse graphs, including bipartite graphs and graphs with small edge weight, where the edge weight of a graph is defined by max{d(G)(u)+ d(G)(v)|uv is an element of E(G)}. We show that: (1) if G is a bipartite graph with bipartition ( A, B) such that Delta(A) = 2 and Delta(B) = Delta >= 4, then G has strong list-chromatic index atmost 3 Delta -3; (2) every graph with edge weight at most 5 (resp. 6) has strong list-chromatic index at most 7 (resp. 11) and every planar graph with edge weight at most 6 has strong list-chromatic index at most 10; and (3) every graph with edge weight at most 7 has strong list-chromatic index at most 16.

Automated summary

This paper investigates the list version of strong edge-colorings in several classes of sparse graphs, including bipartite graphs and graphs with small edge weights. The paper presents properties and bounds for the list version of strong edge-colorings.