平面图的无圈边染色

Acyclic Edge Coloring of Planar Graphs

摘要: 对千图 G 的一个边染色 c : E(G) → {1, 2, . . . , k}，若满足任意两条相邻边都染不同的颜色，且图G 不存在双色圈，则 c 称为图 G 的一个无圈 k-边染色。图 G 的无圈边色数为使得图 G 有一个无圈 k-边染色的最小正整数 k，用X_a^'(G) 表示。本文主要证明了若图 G 是不含相邻 i-圈，且 5-， j-圈不邻的平面图，i ∈ {3, 4}, j ∈ {4, 6}，则X_a^'(G) ≤ ∆(G) + 2。

Abstract: A proper edge k-coloring is a mapping c : E(G) → {1, 2, . . . , k} such that any two adjacent edges receive different colors. A proper edge k-coloring c of G is called acyclic if there are  no  bichromatic  cycles  in  G. The  acyclic  chromatic  index  of  G, denoted  by X_a^'(G), is the smallest integer k such that G is acyclically edge k-colorable. In this paper, we show that if G is a planar graph containing no adjacent i-cycles and without a 5-cycle adjacent  to  a  j-cycle, i ∈ {3, 4}, j ∈ {4, 6}, then X_a^'(G) ≤ ∆(G) + 2.