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 - 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).
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
SN - 0195-6698
VL - 67
SP - 21
EP - 39
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -