Name
Abstract | ||
|---|---|---|
A strong
k-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). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ejc.2017.06.001 | European Journal of Combinatorics |
Field | DocType | Volume |
Integer,Discrete mathematics,Edge coloring,Graph,Degenerate energy levels,Combinatorics,Bound graph,Degree (graph theory),Mathematics | Journal | 67 |
ISSN | Citations | PageRank |
0195-6698 | 1 | 0.42 |
References | Authors | |
15 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilkyoo Choi | 1 | 26 | 12.04 |
| Jae-Hoon Kim | 2 | 268 | 65.73 |
| Alexandr V. Kostochka | 3 | 682 | 89.87 |
| André Raspaud | 4 | 850 | 85.91 |