Strong Chromatic Index of Chordless Graphs |
| |
| Authors: | Manu Basavaraju Mathew C Francis |
| |
| Institution: | 1. DEPARTMENT OF INFORMATICS, UNIVERSITY OF BERGEN, NORWAYContract grant sponsor: European Research Council (ERC) Grant “Rigorous Theory of Preprocessing,” reference 267959 (to M.B.);2. COMPUTER SCIENCE UNIT, INDIAN STATISTICAL INSTITUTE (ISI), CHENNAI, INDIAContract grant sponsors: Institute of Mathematical Sciences, Chennai and the INSPIRE Faculty Award of the Department of Science and Technology, Government of India, reference IFA12–ENG–21 (to M.C.F.). |
| |
| Abstract: | A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by  , is the minimum number of colors needed in any strong edge coloring of G. A graph is said to be chordless if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp, and Tuza (The Strong Chromatic Index of Graphs, Ars Combin 29B (1990), 205–211) considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan (Strong Chromatic Index of 2‐degenerate Graphs, J Graph Theory, 73(2) (2013), 119–126) answered this question in the affirmative by proving that if G is a chordless graph with maximum degree Δ, then  . We improve this result by showing that for every chordless graph G with maximum degree Δ,  . This bound is tight up to an additive constant. |
| |
| Keywords: | strong edge coloring chordless graphs strong chromatic index induced matching |
|
|
