平面图的无圈边染色  

Acyclic Edge Coloring of Planar Graphs

作　　者：贾琪 朱洪国 

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江 金华

出　　处：《应用数学进展》2021年第8期2660-2672,共13页Advances in Applied Mathematics

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

关 键 词：无圈边染色 平面图 圈 

分 类 号：O15[理学—数学]