谢德政,吴燕青.不含相邻三角形的平面图的无圈边着色[J].数学研究及应用,2012,32(4):407~414
不含相邻三角形的平面图的无圈边着色
Acyclic Edge Coloring of Planar Graphs without Adjacent Triangles
投稿时间:2010-07-07  最后修改时间:2011-12-19
DOI:10.3770/j.issn:2095-2651.2012.04.004
中文关键词:  无圈边着色  无圈边色数  平面图.
英文关键词:acyclic edge coloring  acyclic edge chromatic number  planar graph.
基金项目:
作者单位
谢德政 重庆大学数学与统计学院, 重庆 401331 
吴燕青 重庆大学数学与统计学院, 重庆 401331; 山西师范大学数学与计算机科学学院, 山西 临汾 041000 
摘要点击次数: 1660
全文下载次数: 1706
中文摘要:
      图$G$的一个无圈边着色是一个正常的边着色且不含双色的圈.图$G$的无圈边色数是图$G$的无圈边着色中所用色数的最小者,用$\chi'_{a}(G)$表示. 本文证明了如果$G$是一个不含相邻三角形的平面图,那么$\chi'_{a}(G)\leq \Delta(G)+5$.
英文摘要:
      An acyclic edge coloring of a graph $G$ is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic edge chromatic number} of a graph $G$ is the minimum number $k$ such that there exists an acyclic edge coloring using $k$ colors and is denoted by $\chi'_{a}(G)$. In this paper we prove that $\chi'_{a}(G)\leq \Delta(G)+5$ for planar graphs $G$ without adjacent triangles.
查看全文  查看/发表评论  下载PDF阅读器