Improved Upper Bounds on Acyclic Edge Colorings

CSpace > 应用数学研究所

	Improved Upper Bounds on Acyclic Edge Colorings
其他题名	Improved upper bounds on acyclic edge colorings
	Wu Yuwen 1; Yan Guiying2
	2014-01-01
发表期刊	ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
ISSN	0168-9673
卷号	30 期号:2 页码:305-308
摘要	An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a'(G) <= 16 del for every graph G where del denotes the maximum degree of G. We prove that a'(G) < 13.8 del for an arbitrary graph G. We also reduce the upper bounds of a'(G) to 9.8 del and 9 del with girth 5 and 7, respectively.
其他摘要	Abstract(#br)An a cyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The a cyclic chromatic index of a graph G , denoted by a ′( G ), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a ′( G ) ≤ 16Δ for every graph G where Δ denotes the maximum degree of G . We prove that a ′( G ) < 13.8Δ for an arbitrary graph G . We also reduce the upper bounds of a ′( G ) to 9.8Δ and 9Δ with girth 5 and 7, respectively.
关键词	graph coloring acyclic edge coloring Lovasz local lemma
收录类别	CSCD
语种	英语
资助项目	[National Natural Science Foundation of China]
CSCD记录号	CSCD:5102536
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/54755
专题	应用数学研究所
作者单位	1.北京物资学院 2.中国科学院数学与系统科学研究院
推荐引用方式 GB/T 7714	Wu Yuwen,Yan Guiying. Improved Upper Bounds on Acyclic Edge Colorings[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2014,30(2):305-308.
APA	Wu Yuwen,&Yan Guiying.(2014).Improved Upper Bounds on Acyclic Edge Colorings.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,30(2),305-308.
MLA	Wu Yuwen,et al."Improved Upper Bounds on Acyclic Edge Colorings".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 30.2(2014):305-308.