论文标题
稀疏图和平面图的奇数着色
Odd coloring of sparse graphs and planar graphs
论文作者
论文摘要
图形的{\ it Odd $ c $ -oloring}是适当的$ c $ - 颜色，因此每个非分离顶点在其附近都有奇数次数。这个概念是最近由Petru \ V Sevski和\ V Skrekovski引入的，引起了极大的关注。克兰斯顿（Cranston）调查了具有最高平均水平的图形的奇数色彩，并推测每个图$ g $带有$ mad（g）\ leq \ frac {4c-4} {4c-4} {C+1} $都有一个奇数$ c $ -c $ -c $ -c $ -c \ geq 4 $，并以$ c \ in \ in \ in \ in \ c \ cy证明了推测为$ c \ in \ in \ c} = 5，6 \} $。特别是，带有腰围至少$ 7 $和$ 6 $的平面图分别具有奇怪的$ 5 $颜色和奇怪的$ 6 $颜色。 我们完全解决了克兰斯顿的猜想。对于$ c \ geq 7 $，我们证明了猜想是正确的，以更强的形式被Cranston暗示，但是对于$ c = 4 $，我们构建了反例，这些都包含$ 5 $ -CYCLES。另一方面，我们证明了带有$ mad（g）<\ frac {22} {9} $的图$ g $，并且没有诱导的$ 5 $ -CYCLES具有奇数$ 4 $ - 颜色。这意味着带有腰围至少11个的平面图具有奇怪的$ 4 $颜色。我们还证明，带有腰围至少5个的平面图具有奇怪的$ 6 $颜色。
An {\it odd $c$-coloring} of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing an odd number of times on its neighborhood. This concept was introduced very recently by Petru\v sevski and \v Skrekovski and has attracted considerable attention. Cranston investigated odd colorings of graphs with bounded maximum average degree, and conjectured that every graph $G$ with $mad(G)\leq \frac{4c-4}{c+1}$ has an odd $c$-coloring for $c\geq 4$, and proved the conjecture for $c\in\{5, 6\}$. In particular, planar graphs with girth at least $7$ and $6$ have an odd $5$-coloring and an odd $6$-coloring, respectively. We completely resolve Cranston's conjecture. For $c\geq 7$, we show that the conjecture is true, in a stronger form that was implicitly suggested by Cranston, but for $c=4$, we construct counterexamples, which all contain $5$-cycles. On the other hand, we show that a graph $G$ with $mad(G)<\frac{22}{9}$ and no induced $5$-cycles has an odd $4$-coloring. This implies that a planar graph with girth at least 11 has an odd $4$-coloring. We also prove that a planar graph with girth at least 5 has an odd $6$-coloring.
