首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Acyclic edge coloring of graphs with large girths
Authors:QiZhong Lin  JianFeng Hou  Yue Liu
Institution:1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, 350108, China
2. Center for Discrete Mathematics, Fuzhou University, Fuzhou, 350003, China
Abstract:A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by x?? a (G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree ?? and girth g(G), and let 1 ? r ? 2?? be an integer. In this paper, it is shown that there exists a constant c > 0 such that if $g(G) \geqslant \frac{{c\Delta }} {r}\log \left( {\Delta ^2 /r} \right)$ then x?? a (G) ? ??+r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that x?? a (G) = ?? if ?? ? 4 and g(G) ? 4; or ?? ? 3 and g(G) ? 5.
Keywords:
本文献已被 CNKI SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号