The Strong Chromatic Index of graphs with maximum degree \Delta

Abstract: A strong edge-coloring of a graph

G

is an edge-coloring such that no two edges of distance at most two receive the same color. The strong chromatic index

c h i'_{s} (G)

is the minimum number of colors in a strong edge-coloring of

G

. P. ErdH{o}s and J. Nev{s}etv{r}il conjectured in 1985 that

c h i'_{s} (G)

is bounded above by

f r a c 54 D e l t a^{2}

when

D e l t a

is even and

f r a c 14 (5 D e l t a^{2} - 2 D e l t a + 1)

when

D e l t a

is odd, where

D e l t a

is the maximum degree of

G

. In this paper, we give an algorithm that uses at most

2 D e l t a^{2} - 3 D e l t a + 2

colors for graphs with girth at least

5

. And in particular, we prove that any graph with maximum degree

D e l t a = 5

has a strong edge-coloring with

37

colors.

This page was built for publication: The Strong Chromatic Index of graphs with maximum degree $\Delta$