论文标题
稀疏图的奇数颜色
Odd Colorings of Sparse Graphs
论文作者
论文摘要
如果每个非分离顶点都有某种颜色在其邻域上显示出奇数的次数，则称为图的适当着色称为\ emph {奇数}。承认图形$ g $的奇数颜色的最少数量的颜色表示为$χ_o（g）$。这一概念是由Petruševski和škrekovski引入的，他们证明了如果$ G $是平面，则$χ_o（g）\ le 9 $;他们还推测$χ_o（g）\ le 5 $。对于正实数$α$，我们考虑所有图$ g $的最大值$χ_o（g）$，最大平均度小于$α$；我们用$χ_o（\ Mathcal {G}_α）$表示此值。我们注意到，对于所有$α\ ge 4 $，$χ_o（\ Mathcal {G}_α）$均未定义。相比之下，对于[0,4）$中的每个$α\，我们在$χ_o（\ Mathcal {g}_α）$上给出了（几乎尖锐的）上限。最后，我们证明$χ_o（\ Mathcal {G} _ {20/7}）= 5 $和$χ_O（\ Mathcal {G} _3）= 6 $。这两个结果都很清晰。
A proper coloring of a graph is called \emph{odd} if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. The smallest number of colors that admits an odd coloring of a graph $G$ is denoted $χ_o(G)$. This notion was introduced by Petruševski and Škrekovski, who proved that if $G$ is planar then $χ_o(G)\le 9$; they also conjectured that $χ_o(G)\le 5$. For a positive real number $α$, we consider the maximum value of $χ_o(G)$ over all graphs $G$ with maximum average degree less than $α$; we denote this value by $χ_o(\mathcal{G}_α)$. We note that $χ_o(\mathcal{G}_α)$ is undefined for all $α\ge 4$. In contrast, for each $α\in[0,4)$, we give a (nearly sharp) upper bound on $χ_o(\mathcal{G}_α)$. Finally, we prove $χ_o(\mathcal{G}_{20/7})= 5$ and $χ_o(\mathcal{G}_3)= 6$. Both of these results are sharp.
