Strong edge-colorings of sparse graphs with large maximum degree

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

Research output: Contribution to journalArticle

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

Fingerprint

Graph in graph theory
Edge coloring
Maximum degree
Adjacent
Chromatic index
Sparse graphs
Restriction
Distinct
Integer

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Cite this

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

In: European Journal of Combinatorics, Vol. 67, 01.01.2018, p. 21-39.

Research output: Contribution to journalArticle

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

In: European Journal of Combinatorics, Vol. 67, 01.01.2018, p. 21-39.

Research output: Contribution to journalArticle

@article{92eb7cd02bda4ee2bb9d9627e991f259,
title = "Strong edge-colorings of sparse graphs with large maximum degree",
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).",
author = "Ilkyoo Choi and Jaehoon Kim and Kostochka, {Alexandr V.} and André Raspaud",
year = "2018",
month = "1",
doi = "10.1016/j.ejc.2017.06.001",
volume = "67",
pages = "21--39",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",

}

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 -