We consider single-conflict colorings, a variant of graph colorings in which each edge of a graph has a single forbidden color pair. We show that for any assignment of forbidden color pairs to the edges of a $d$-degenerate graph $G$ on $n$ vertices of edge-multiplicity at most $\log \log n$, $O(\sqrt{ d } \log n)$ colors are always enough to color the vertices of $G$ in a way that avoids every forbidden color pair. This answers a question of Dvo\v{r}\'ak, Esperet, Kang, and Ozeki for simple graphs (Journal of Graph Theory 2021).
翻译：我们考虑的是单冲突色, 图形颜色的变体, 图表的每个边缘都有单一的被禁止的颜色配对。 我们显示, 任何将禁止的颜色配对分配到 $d$- degenerate 图形边缘的一对 $G$, 以 $ log\ log n$, $O( sqrt{ d}\ log n) $ $) 彩色最多, $O (sqrt{ d}\ log n) $, 一直足够在 $G 的顶端上涂色, 以避免每种被禁止的颜色配对。 这回答了 Dvo\ v{r\\\ { Qak, Esperet, Kang 和 Ozeki 的简单图形问题( 图理学杂志 2021 ) 。
相关内容
微信扫码咨询专知VIP会员