作者机构:[Wang, Yiqiao] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China.; [Shu, Qiaojun] Hangzhou Dianzhi Univ, Sch Sci, Hangzhou 3 更多[Wang, Yiqiao] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China.; [Shu, Qiaojun] Hangzhou Dianzhi Univ, Sch Sci, Hangzhou 310018, Zhejiang, Peoples R China.; [Wu, Jian-Liang; Zhang, Wenwen] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China. 收起
来源:JOURNAL OF COMBINATORIAL OPTIMIZATION
出版年:2014
卷:28
期:3
页码:692-715
DOI:10.1007/s10878-014-9765-6
关键词:Acyclic edge coloring; Planar graph Cycles; Maximum degree
摘要:An acyclic edge coloring of a graph is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of is the smallest integer such that has an acyclic edge coloring using colors. Fiam ik (Math Slovaca 28:139-145, 1978) and later Alon et al. (J Graph Theory 37:157-167, 2001) conjectured that for any simple graph with maximum degree . In this paper, we confirm this conjecture for planar graphs without a -cycle adjacent to a -cycle.