Premium
Star Chromatic Index
Author(s) -
Dvořák Zdeněk,
Mohar Bojan,
Šámal Robert
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.21644
Subject(s) - mathematics , combinatorics , mathematical proof , chromatic scale , upper and lower bounds , star (game theory) , edge coloring , graph , discrete mathematics , graph power , line graph , geometry , mathematical analysis
The star chromatic indexχ s ′ ( G )of a graph G is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi‐colored. We obtain a near‐linear upper bound in terms of the maximum degree Δ = Δ ( G ) . Our best lower bound on χ s ′ in terms of Δ is 2 Δ ( 1 + o ( 1 ) ) valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.