List strong edge-coloring of graphs with maximum degree 4

Abstract: A strong edge-coloring of a graph

G

is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by

c h i_{s^{'}} (G)

which is the minimum number of colors that allow a strong edge-coloring of

G

. ErdH{o}s and Nev{s}etv{r}il conjectured in 1985 that the upper bound of

c h i_{s^{'}} (G)

is

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

. The conjecture is proved right when

D e l t a l e q 3

. The best known upper bound for

D e l t a = 4

is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when

D e l t a = 4

the upper bound of list strong chromatic index is 22.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: List strong edge-coloring of graphs with maximum degree 4