论文标题
在稀疏图的奇数上
On odd colorings of sparse graphs
论文作者
论文摘要
图形的\ emph {奇数$ c $ - 颜色}是适当的$ c $ - 颜色，因此每个非分离顶点的颜色在其开放式社区内显示出奇数次。图形的A \ emph {适当的无冲突$ c $ - 颜色}是一个适当的$ c $ - 颜色，因此每个非分离顶点的颜色恰好在其附近出现一次。显然，每一个适当的无冲突$ c $ - 颜色也是一种奇怪的$ c $颜色。克兰斯顿（Cranston）指出，每个图$ g $均具有最高平均度$ \ text {mad}（g）<\ frac {4c} {c+2} $（其中$ c \ geq 4 $）具有奇数$ c $ coloring，他证明了$ c \ in \ in \ in \ in \ {5，6 \ 6 \ \ \ 6 \ c的$ c \ cy c \ in。请注意，最好的可能是绑定的$ \ frac {4c} {C+2} $。 Cho等。解决了克兰斯顿（Cranston）对$ c \ geq 5 $的猜想，从而通过从奇数$ c $颜色到适当的无冲突$ c $颜色来加强结果。但是，他们没有提供$ \ text {mad}（g）= \ frac {4c} {c+2} $的所有极端非色图$ g $，这仍然是一个开放的利益问题。 在本文中，我们解决了这个有趣的极端问题。我们的目标是表征所有非宣传冲突$ C $ -Colorable Graphs $ g $，$ \ text {mad}（g）= \ frac {4c} {c+2} $。对于$ c = 4 $的情况，克兰斯顿的猜想是不正确的，如存在反例的存在所证明的：每个块的图形都是$ 5 $ - 周期。 Cho等人证明了带有$ \ text {mad}（g）<\ frac {22} {9} $的图$ g $，并且没有诱导的$ 5 $ -CYCLES具有奇数$ 4 $ - 颜色。我们通过证明具有$ \ text {mad}（g）\ leq \ frac {22} {9} $的图$ g $（允许等于公平）的图形$ g $不是奇怪的$ 4 $ - 可油时，并且仅当$ g $属于特定图形时。另一方面，Cho等人确定了带有腰围至少$ 5 $的平面图具有奇怪的$ 6 $颜色；我们通过证明没有$ 4^{ - } $的平面图与$ 7^{ - } $相邻的平面图也有一个奇数$ 6 $ - 颜色。
An \emph{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 within its open neighborhood. A \emph{proper conflict-free $c$-coloring} of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing exactly once within its neighborhood. Clearly, every proper conflict-free $c$-coloring is also an odd $c$-coloring. Cranston conjectured that every graph $G$ with maximum average degree $\text{mad}(G) < \frac{4c}{c+2}$ (where $c \geq 4$) has an odd $c$-coloring, and he proved this conjecture for $c \in \{5, 6\}$. Note that the bound $\frac{4c}{c+2}$ is best possible. Cho et al. solved Cranston's conjecture for $c \geq 5$, strengthening the result by transitioning from odd $c$-coloring to proper conflict-free $c$-coloring. However, they did not provide all the extremal non-colorable graphs $G$ with $\text{mad}(G) = \frac{4c}{c+2}$, which remains an open question of interest. In this paper, we tackle this intriguing extremal problem. We aim to characterize all non-proper conflict-free $c$-colorable graphs $G$ with $\text{mad}(G) = \frac{4c}{c+2}$. For the case of $c=4$, Cranston's conjecture is not true, as evidenced by the existence of a counterexample: a graph whose every block is a $5$-cycle. Cho et al.\ proved that a graph $G$ with $\text{mad}(G) < \frac{22}{9}$ and no induced $5$-cycles has an odd $4$-coloring. We improve this result by proving that a graph $G$ with $\text{mad}(G) \leq \frac{22}{9}$ (with equality allowed) is not odd $4$-colorable if and only if $G$ belongs to a specific class of graphs. On the other hand, Cho et al.\ established that a planar graph with girth at least $5$ has an odd $6$-coloring; we improve it by proving that a planar graph without $4^{-}$-cycles adjacent to $7^{-}$-cycles also has an odd $6$-coloring.
