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 条
  • [1] Alon N.(1991)A parallel algorithmic version of the local lemma Random Struct Algor 2 367-378
  • [2] Alon N.(2001)Acyclic edge colorings of graphs J Graph Theory 37 157-167
  • [3] Sudakov B.(2008)Acyclic edge coloring of subcubic graphs Discrete Math 308 6650-6653
  • [4] Zaks A.(2009)Acyclic edge coloring of graphs with maximum degree 4 J Graph Theory 61 192-209
  • [5] Basavaraju M.(1986)The acyclic coloring problem and estimation of spare Hession matrices SIAM J Algebr Discrete Math 7 221-235
  • [6] Chandran L. S.(1984)Estimation of spare Hession matrices and graph coloring problems Math Prog 28 243-270
  • [7] Basavaraju M.(1965)Topology of series-parallel networks J Math Anal Appl 10 303-318
  • [8] Chandran L. S.(2004)Star coloring of graphs J Graph Theory 47 163-182
  • [9] Coleman T. F.(2009)Acyclic edge colorings of planar graphs and seriell-parallel graphs Sci China Ser A 52 605-616
  • [10] Cai J.(2010)Acyclic edge chromatic number of outerplanar graphs J Graph Theory 64 22-36