List Strong Edge-Colorings of Sparse Graphs

Document Type

Article

Publication Date

11-1-2023

Identifier/URL

40974211 (Pure)

Abstract

A strong edge-coloring of a graph G = (V , E) is a partition of its edge set E into induced matchings. In this paper, we will 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) | u v ∈ E (G) } . We show that: (1) if G is a bipartite graph with bipartition (A, B) such that Δ (A) = 2 and Δ (B) = Δ ≥ 4 , then G has strong list-chromatic index at most 3 Δ - 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.

Comments

Publisher Copyright: © 2023, The Author(s), under exclusive licence to Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia.

DOI

10.1007/s40840-023-01594-z

Link to Full Text

Find in your library

Off-Campus WSU Users


Share

COinS