论文标题
平面图中的圆形着色和分数着色
Circular Coloring and Fractional Coloring in Planar Graphs
论文作者
论文摘要
我们在循环着色方面研究了以下steinberg型问题：对于一个奇数的整数$ k \ ge 3 $，最小的数字$ f（k）$是什么，以至于每个平面图$ k $ of $ k+k+k+k+1 $ to $ k+1 $ f（$ f（k）$ c_k $ c_k $ c_k $（或equartival）的循环的长度是$ k+1 $ f（k） $（k，\ frac {k-1} {2}）$ - 可着色）。 Steinberg的猜想中的已知结果和反例表明$ f（3）\ in \ {6,7 \} $。在本文中，我们表明$ f（k）$存在且仅当$ k $是一个奇怪的素数时。此外，我们证明，对于任何质量$ p \ ge 5 $，$$ p^2- \ frac {5} {2} {2} p+\ frac {3} {2} {2} {2} \ le f（p）\ le 2p^2+2p^2+2p-5。$ $ $ Girth $ 2P-2 $的平面图具有同构为$ C_P $的任何Prime $ P \ ge 5 $。在支持这个猜想的情况下，我们证明了相关的分数颜色，每个平面图$ k $的每个平面图都没有长度从$ k+1 $到$ \ lfloor \ lfloor \ frac {22k} {3} {3} \ rfloor $的$（k：k：\ frac {k-1} $ ge 5 $ k $ ge ge for nist ock for 5 $ ke frac {3} {3} \ rfloor $。
We study the following Steinberg-type problem on circular coloring: for an odd integer $k\ge 3$, what is the smallest number $f(k)$ such that every planar graph of girth $k$ without cycles of length from $k+1$ to $f(k)$ admits a homomorphism to the odd cycle $C_k$ (or equivalently, is circular $(k,\frac{k-1}{2})$-colorable). Known results and counterexamples on Steinberg's Conjecture indicate that $f(3)\in\{6,7\}$. In this paper, we show that $f(k)$ exists if and only if $k$ is an odd prime. Moreover, we prove that for any prime $p\ge 5$, $$p^2-\frac{5}{2}p+\frac{3}{2}\le f(p)\le 2p^2+2p-5.$$ We conjecture that $f(p)\le p^2-2p$, and observe that the truth of this conjecture implies Jaeger's conjecture that every planar graph of girth $2p-2$ has a homomorphism to $C_p$ for any prime $p\ge 5$. Supporting this conjecture, we prove a related fractional coloring result that every planar graph of girth $k$ without cycles of length from $k+1$ to $\lfloor\frac{22k}{3}\rfloor$ is fractional $(k:\frac{k-1}{2})$-colorable for any odd integer $k\ge 5$.
