Premium
Strong Chromatic Index of 2‐Degenerate Graphs
Author(s) -
Chang Gerard Jennhwa,
Narayanan N.
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21646
Subject(s) - combinatorics , mathematics , chromatic scale , degenerate energy levels , chordal graph , graph , indifference graph , discrete mathematics , physics , quantum mechanics
We prove that the strong chromatic index of a 2‐degenerate graph is linear in the maximum degree Δ. This includes the class of all chordless graphs (graphs in which every cycle is induced) which in turn includes graphs where the cycle lengths are multiples of four, and settles a problem by Faudree et al. (Ars Combin 29(B) (1990), 205–211). © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 119–126, 2013