A Bound on the Strong Chromatic Index of a Graph

✍ Scribed by Michael Molloy; Bruce Reed

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 695 KB
• Volume: 69
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1724

✦ Synopsis

We show that the strong chromatic index of a graph with maximum degree 2 is at most (2&=) 2 2 , for some =>0. This answers a question of Erdo s and Nes etr il.

1997 Academic Press

1. Introduction

A strong edge-colouring of a (simple) graph, G, is a proper edge-colouring of G with the added restriction that no edge is adjacent to two edges of the same colour. (Note that in any proper edge-colouring of G, no edge is adjacent to three edges of the same colour.) Equivalently, it is a proper vertex-colouring of L(G) 2 , the square of the line graph of G. 1 The strong chromatic index of G, s/$(G), is the least integer k such that G has a strong edge-colouring using k colours.

If G has maximum degree 2, then trivially s/$(G) 22 2 &22+1, as L(G) 2 has maximum degree at most 22 2 &22. In 1985, Erdo s and Nes etr il (see [5]) asked if there is any =>0 such that, for every such G, s/$(G) (2&=) 2 2 . They pointed out that by multiplying the vertices of the 5-cycle, one can obtain a graph, G, with arbitrarily large 2 for which s/$(G)= 5 4 2 2 , and also conjectured that, in fact, for every G with maximum article no. TB971724 103 0095-8956Â97 25.00