Acyclic edge coloring of graphs with large girths |
| |
Authors: | QiZhong Lin JianFeng Hou Yue Liu |
| |
Affiliation: | 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{{cDelta }} {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 等数据库收录! |
|