Embeddings of a Graph into a Surface with Different Weak Chromatic Numbers
Embeddings of a Graph into a Surface with Different Weak Chromatic Numbers
复制标题
DOI：
10.1007/s00373-020-02256-8
复制
发表时间：
2020-11
影响因子：
0.7
通讯作者：
Kengo Enami;Kenta Noguchi
中科院分区：
文献类型：
--
作者：
Kengo Enami;Kenta Noguchi
图G嵌入曲面的弱染色是G的顶点染色，使得没有面是单色的。G的弱色数是使G具有弱k-染色的最小数k。Kündgen和Ramamurthi（J Combin Theory Ser B 85，307-337，2002）证明了对于每个正整数k，存在一个图，该图在同一个曲面上有两个不同的嵌入，其弱色数至少相差k。本文从两个方面肯定地回答了这一猜想。
A weak coloring of a graphGembedded on a surface is a vertex coloring ofGsuch that no face is monochromatic. The weak chromatic number ofGis the minimum numberksuch thatGhas a weakk-coloring. Kündgen and Ramamurthi (J Combin Theory Ser B 85, 307–337, 2002) conjectured that for each positive integerk, there is a graph that has two different embeddings on the same surface whose weak chromatic numbers differ by at leastk. In this paper, we answer this conjecture affirmatively in two ways.