Star chromatic index

Details Star chromatic index Star chromatic index

2010-11-15

arxiv.org/abs/1011.3376v2

Mathematics

Combinatorics

16 pages, 3 figures

Scientific paper

The star chromatic index $\chi_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 $\Delta=\Delta(G)$. Our best lower bound on $\chi_s'$ in terms of $\Delta$ is $2\Delta(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.

Affiliated with

Also associated with

No associations

Rating

Star chromatic index does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Star chromatic index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Star chromatic index will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-298759