The sharp degree bound for strong edge-colouring
Let $G$ be a finite multigraph without loops and with at least one edge, and let $\Delta$ be its maximum degree, counting parallel edges. A strong edge-colouring of $G$ gives distinct colours to any two distinct edges that share an endpoint or are both incident to a third edge; $\chi'_s(G)$ is the least number of colours in a strong edge-colouring, so that $\chi'_s(G) = \chi(L(G)^2)$. Replacing the vertices of a five-cycle by independent sets of sizes $\Delta/2$ ($\Delta$ even), or of sizes $(\Delta+1)/2$ at two consecutive vertices and $(\Delta-1)/2$ at the other three ($\Delta \ge 3$ odd), and each edge of the cycle by all edges between the two sets, gives graphs in which every two edges conflict and whose number of edges is the bound below. Andersen, and independently Horák, He and Trotter, proved the bound for $\Delta = 3$, and Huang, Santana and Yu proved $\chi'_s(G) \le 21$ for $\Delta = 4$. Hurley, de Joannis de Verclos and Kang proved $\chi'_s(G) \le 1.772\,\Delta^2$ for simple graphs of sufficiently large maximum degree.
Problem. Is $$\chi'_s(G) \le \begin{cases} \dfrac{5\Delta^2}{4}, & \Delta \text{ even}, \\[4pt] \dfrac{5\Delta^2 - 2\Delta + 1}{4}, & \Delta \text{ odd}, \end{cases}$$ for every such $G$?
Source: Erdős and Nešetřil (1985); see Erdős (1988). In this form, for graphs with parallel edges allowed, Faudree, Schelp, Gyárfás and Tuza (1990), Conjecture 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, Erdős–Nešetřil conjecture, strong chromatic index, strong edge-colourings
References
@article{faudree1990,
author = {Faudree, R. J. and Schelp, R. H. and Gy{\'a}rf{\'a}s, A. and Tuza, Zs.},
title = {The strong chromatic index of graphs},
journal = {Ars Combin.},
volume = {29},
number = {B},
year = {1990},
pages = {205--211},
}
@article{erdos1988,
author = {Erd{\H{o}}s, Paul},
title = {Problems and results in combinatorial analysis and graph theory},
journal = {Discrete Math.},
volume = {72},
number = {1--3},
year = {1988},
pages = {81--92},
doi = {10.1016/0012-365X(88)90196-3},
}
@article{andersen1992,
author = {Andersen, Lars D{\o}vling},
title = {The strong chromatic index of a cubic graph is at most 10},
journal = {Discrete Math.},
volume = {108},
number = {1--3},
year = {1992},
pages = {231--252},
doi = {10.1016/0012-365X(92)90678-9},
}
@article{horak1993,
author = {Hor{\'a}k, Peter and He, Qing and Trotter, William T.},
title = {Induced matchings in cubic graphs},
journal = {J. Graph Theory},
volume = {17},
number = {2},
year = {1993},
pages = {151--160},
doi = {10.1002/jgt.3190170204},
}
@article{huang2018,
author = {Huang, Mingfang and Santana, Michael and Yu, Gexin},
title = {Strong chromatic index of graphs with maximum degree four},
journal = {Electron. J. Combin.},
volume = {25},
number = {3},
year = {2018},
pages = {P3.31},
doi = {10.37236/7016},
}
@article{hurley2022,
author = {Hurley, Eoin and de Joannis de Verclos, R{\'e}mi and Kang, Ross J.},
title = {An improved procedure for colouring graphs of bounded local density},
journal = {Adv. Comb.},
year = {2022},
pages = {Paper No. 7, 33 pp.},
doi = {10.19086/aic.2022.7},
eprint = {2007.07874},
archivePrefix = {arXiv},
}
@misc{aim-strong-edge-colouring,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp degree bound for strong edge-colouring}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/344-strong-edge-colouring.md},
note = {Entry 344 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00563, "The sharp degree bound for strong edge-colouring", clopen.solutions.