### Abstract

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).

Original language | English (US) |
---|---|

Pages (from-to) | 21-39 |

Number of pages | 19 |

Journal | European Journal of Combinatorics |

Volume | 67 |

DOIs | |

State | Published - Jan 1 2018 |

### Fingerprint

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics

### Cite this

*European Journal of Combinatorics*,

*67*, 21-39. DOI: 10.1016/j.ejc.2017.06.001

**Strong edge-colorings of sparse graphs with large maximum degree.** / Choi, Ilkyoo; Kim, Jaehoon; Kostochka, Alexandr V.; Raspaud, André.

Research output: Contribution to journal › Article

*European Journal of Combinatorics*, vol 67, pp. 21-39. DOI: 10.1016/j.ejc.2017.06.001

}

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é

PY - 2018/1/1

Y1 - 2018/1/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

VL - 67

SP - 21

EP - 39

JO - European Journal of Combinatorics

T2 - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -