Strong edge-colorings of sparse graphs with large maximum degree

Ilkyoo Choi, Jaehoon Kim, Alexandr V. Kostochka, André Raspaud

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)21-39
Number of pages19
JournalEuropean Journal of Combinatorics
Volume67
DOIs
StatePublished - Jan 2018

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Strong edge-colorings of sparse graphs with large maximum degree'. Together they form a unique fingerprint.

Cite this