Acyclic edge coloring of graphs with large girths

被引:0
作者
QiZhong Lin
JianFeng Hou
Yue Liu
机构
[1] Fuzhou University,College of Mathematics and Computer Science
[2] Fuzhou University,Center for Discrete Mathematics
来源
Science China Mathematics | 2012年 / 55卷
关键词
acyclic edge coloring; girth; probability method; series-parallel graphs; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g(G) \geqslant \frac{{c\Delta }} {r}\log \left( {\Delta ^2 /r} \right)$$\end{document} 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.
引用
收藏
页码:2593 / 2600
页数:7
相关论文
共 36 条
[31]  
Subramanian C. R.(undefined)undefined undefined undefined undefined-undefined
[32]  
Skulrattanakulchai S.(undefined)undefined undefined undefined undefined-undefined
[33]  
Spencer J.(undefined)undefined undefined undefined undefined-undefined
[34]  
Vizing V. G.(undefined)undefined undefined undefined undefined-undefined
[35]  
Wu J.(undefined)undefined undefined undefined undefined-undefined
[36]  
Wu Y.(undefined)undefined undefined undefined undefined-undefined