PreprintarXiv licencearXiv
Strong edge coloring of graphs with maximum degree $6$
Abstract
Let G be a graph. Under a strong edge coloring of G, every color class is an induced matching. The strong chromatic index of G, denoted by χ's(G), is the smallest integer k such that G admits a strong edge coloring with k colors. Denote by Δ(G) the maximum degree of G. In this paper, we prove that every graph G with Δ(G)≤ 6 satisfies χ's(G)≤ 57, improving the best known upper bound $60$.
Related
- A note on the injective edge coloring of graphs with bounded maximum degree
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- Frugal coloring in planar graphs with maximum degree 4 and 5
- On (1,24) and (1,25)-packing edge-coloring of sparse subcubic graphs
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
BibTeX
@misc{wang2026strong,
title = {{Strong edge coloring of graphs with maximum degree $6$}},
author = {Runze Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33945},
eprint = {2609.33945},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33945},
}
RIS
TY - UNPB
TI - Strong edge coloring of graphs with maximum degree $6$
AU - Runze Wang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33945
UR - https://arxiv.org/abs/2609.33945
AB - Let G be a graph. Under a strong edge coloring of G, every color class is an induced matching. The strong chromatic index of G, denoted by χ'_s(G), is the smallest integer k such that G admits a strong edge coloring with k colors. Denote by Δ(G) the maximum degree of G. In this paper, we prove that every graph G with Δ(G)≤ 6 satisfies χ'_s(G)≤ 57, improving the best known upper bound $60$.
ER -