A Strong Edge-Coloring of Graphs with Maximum Degree 4 Using 22 Colors

Abstract

In 1985, Erdős and Neśetril conjectured that the strong edge-coloring number of a graph is bounded above by $5/4{\Delta }^2$ when $\Delta$ is even and $1/4(5{\Delta }^2-2\Delta +1)$ when $\Delta$ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for $\Delta \le 3$. For $\Delta =4$, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.

arXiv comment9 pages, 4 figures

Cited by in corpus (1)

• Strong edge coloring of subcubic bipartite graphs