Star Chromatic Index

被引:35
作者
Dvorak, Zdenek [1 ]
Mohar, Bojan [2 ]
Samal, Robert [1 ]
机构
[1] Charles Univ Prague, Inst Comp Sci, Prague, Czech Republic
[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
graph coloring; edge coloring; COLORINGS;
D O I
10.1002/jgt.21644
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:313 / 326
页数:14
相关论文
共 16 条
[1]  
Albertson MO, 2004, ELECTRON J COMB, V11
[2]   Acyclic edge colorings of graphs [J].
Alon, N ;
Sudakov, B ;
Zaks, A .
JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167
[3]   ACYCLIC COLORING OF GRAPHS [J].
ALON, N ;
MCDIARMID, C ;
REED, B .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288
[5]   An improved construction of progression-free sets [J].
Elkin, Michael .
ISRAEL JOURNAL OF MATHEMATICS, 2011, 184 (01) :93-128
[6]   Star coloring of graphs [J].
Fertin, G ;
Raspaud, A ;
Reed, B .
JOURNAL OF GRAPH THEORY, 2004, 47 (03) :163-182
[7]  
Green B, 2010, ADDITIVE NUMBER THEORY: FESTSCHRIFT IN HONOR OF THE SIXTIETH BIRTHDAY OF MELVYN B. NATHANSON, P141, DOI 10.1007/978-0-387-68361-4_9
[8]   ACYCLIC COLORINGS OF PLANAR GRAPHS [J].
GRUNBAUM, B .
ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408
[9]   Colouring a graph frugally [J].
Hind, H ;
Molloy, M ;
Reed, B .
COMBINATORICA, 1997, 17 (04) :469-482
[10]   THE NP-COMPLETENESS OF EDGE-COLORING [J].
HOLYER, I .
SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720