On the precise value of the strong chromatic index of a planar graph with a large girth

Publication date 6 September 2018

Abstract: A strong

k

-edge-coloring of a graph

G

is a mapping from

E (G)

to

1, 2, l d o t s, k

such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic index

c h i'_{s} (G)

of a graph

G

is the minimum

k

for which

G

has a strong

k

-edge-coloring. Denote

s i g m a (G) = m a x_{x y i n E (G)} o p e r a t o r n a m e d e g (x) + o p e r a t o r n a m e d e g (y) - 1

. It is easy to see that

s i g m a (G) l e c h i'_{s} (G)

for any graph

G

, and the equality holds when

G

is a tree. For a planar graph

G

of maximum degree

D e l t a

, it was proved that

c h i'_{s} (G) l e 4 D e l t a + 4

by using the Four Color Theorem. The upper bound was then reduced to

4 D e l t a

,

3 D e l t a + 5

,

3 D e l t a + 1

,

3 D e l t a

,

2 D e l t a - 1

under different conditions for

D e l t a

and the girth. In this paper, we prove that if the girth of a planar graph

G

is large enough and

s i g m a (G) g e q D e l t a (G) + 2

, then the strong chromatic index of

G

is precisely

s i g m a (G)

. This result reflects the intuition that a planar graph with a large girth locally looks like a tree.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: On the precise value of the strong chromatic index of a planar graph with a large girth