Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777330 | European Journal of Combinatorics | 2018 | 19 Pages |
Abstract
A strong
k-edge-coloring of a graph G is a mapping from E(G) to {1,2,â¦,k} such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. The strong chromatic index
Ïsâ²(G) of a graph G is the smallest integer k such that G admits a strong k-edge-coloring. We give bounds on Ïsâ²(G) in terms of the maximum degree Î(G) of a graph G when G is sparse, namely, when G is 2-degenerate or when the maximum average degree Mad(G) is small. We prove that the strong chromatic index of each 2-degenerate graph G is at most 5Î(G)+1. Furthermore, we show that for a graph G, if Mad(G)<8â3 and Î(G)â¥9, then Ïsâ²(G)â¤3Î(G)â3 (the bound 3Î(G)â3 is sharp) and if Mad(G)<3 and Î(G)â¥7, then Ïsâ²(G)â¤3Î(G) (the restriction Mad(G)<3 is sharp).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ilkyoo Choi, Jaehoon Kim, Alexandr V. Kostochka, André Raspaud,