Given a multigraph, suppose that each vertex is given a local assignment of $k$ colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least $k$ for which this is always possible given any set of local assignments we call the {\em single-conflict chromatic number} of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus $g$ is $O(g^{1/4}\log g)$ as $g\to\infty$. This is sharp up to the logarithmic factor.
翻译：考虑到一个多面图, 假设每个顶端都配有以美元计值的本地颜色。 我们感兴趣的是, 是否每个顶端选择一种本地颜色, 这样边缘就没有两种本地颜色。 考虑到任何一组本地任务, 我们称之为该图的 ~ em 单冲突色谱编号 。 此参数与分离的可容性和可调适性密切相关 。 我们显示, 嵌入 Euler genus $g 表面的简单图表的单冲突色谱数是 $O (g\\ 1/ 4 ⁇ log g), 也就是$g\to\ infty$ 。 这是精确到对数因素的对数 。
相关内容
微信扫码咨询专知VIP会员