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
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 journal › Article
}
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 -