不含相邻三角形的平面图的无圈边着色

Acyclic Edge Coloring of Planar Graphs without Adjacent Triangles

中文关键词:  无圈边着色  无圈边色数  平面图.

英文关键词:acyclic edge coloring  acyclic edge chromatic number  planar graph.

中文摘要:

      图$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.