论文标题
在循环着色猜想上
On the cyclic coloring conjecture
论文作者
论文摘要
平面图$ g $的循环着色是其顶点的着色，以便与同一脸的顶点具有不同的颜色。平面图$ g $的循环着色中的最小颜色数是其环状色度$χ_c（g）$。令$δ^*（g）$为图$ g $的最大面值。 In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $χ_c(G) \leq \lfloor \frac{3}{2}Δ^*(G)\rfloor$, it is enough to do it for subdivisions of simple $3$-connected plane graphs. 我们从这个受限家庭中发现了图形$ g $的$χ_c（g）$上的四个新不同的上限；它们的三个边界很紧。作为定性，我们已经表明，猜想适用于飞机三角剖分的细分，简单3 $连接的飞机四边形以及简单的3 $连接的平面五角platemations pentaglustaugent at tem vev teble for tem vever tem，适用于常规的额定范围，对于简单的$ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3的额定范围，并具有3 $ 3 $的图形。其最长路径的顶点数量仅由第二度的顶点组成。
A cyclic coloring of a plane graph $G$ is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a plane graph $G$ is its cyclic chromatic number $χ_c(G)$. Let $Δ^*(G)$ be the maximum face degree of a graph $G$. In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph $G$ has $χ_c(G) \leq \lfloor \frac{3}{2}Δ^*(G)\rfloor$, it is enough to do it for subdivisions of simple $3$-connected plane graphs. We have discovered four new different upper bounds on $χ_c(G)$ for graphs $G$ from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple $3$-connected plane quadrangulations, and simple $3$-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple $3$-connected plane graphs of maximum degree at least 10, and for subdivisions of simple $3$-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two.
