TY - JOUR

T1 - Strong edge-colorings of sparse graphs with large maximum degree

AU - Choi, Ilkyoo

AU - Kim, Jaehoon

AU - Kostochka, Alexandr V.

AU - Raspaud, André

N1 - Funding Information:
The first author is supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2015R1C1A1A02036398). The second author is supported by the European Research Council under the European Union's Seventh Framework Programme (FP/2007–2013) / ERC Grant Agreements no. 306349 (J. Kim). The research is conducted while the second author visited University of Illinois Urbana-Champaign as part of BRIDGE Strategic Partnership. Research of the third author is supported in part by NSF grant DMS-1600592 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. Research of the fourth author received financial support from the French State, managed by the French National Research Agency (ANR) within the “Investments for the future” Programme IdEx Bordeaux-CPU (ANR-10-IDEX-03-02).
Publisher Copyright:
© 2017

PY - 2018/1

Y1 - 2018/1

N2 - A strongk-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).

AB - A strongk-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).

UR - http://www.scopus.com/inward/record.url?scp=85026674340&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026674340&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2017.06.001

DO - 10.1016/j.ejc.2017.06.001

M3 - Article

AN - SCOPUS:85026674340

VL - 67

SP - 21

EP - 39

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -