(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface
(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface
复制标题
(1, k)-曲面上周长至少为 5 的图的着色
作者：
Ho‐Jin Choi;Ilkyoo Choi;Jisu Jeong;Geewon Suh
一个图是 (d1,...,dr) －可着色的，如果它的顶点集可以划分为 r 个集合 V1,...,Vr ，使得由 Vi 导出的图的最大度数对于每个 i∈{1,...,r} 至多为 di 。对于给定的对 (g,d1) ，确定最小 d2=d2(g,d1) 使得周长至少为 g 的平面图是 (d1,d2) 可着色的问题引起了人们的极大兴趣。除 (g,d1)=(5,1) 外，所有情况下 d2(g,d1) 的有限性都是已知的。蒙塔西尔和奥赫姆明确询问 d2(5, 1) 是否是有限的。我们对这个问题的回答是肯定的，d2(5,1)≤10；也就是说，我们证明所有周长至少为 5 的平面图都是 (1, 10) 可着色的。此外，我们的证明扩展到这样的陈述：对于欧拉属 γ 的任何曲面 S，都存在 K=K(γ)，其中周长至少为 5 且可嵌入在 S 上的图是 (1, K) 可着色的。另一方面，不存在有限的 k，其中周长至少为 5 的平面图（因此可嵌入到任何表面上）是 (0, k) 可着色的。
A graph is (d1,...,dr) ‐colorable if its vertex set can be partitioned into r sets V1,...,Vr so that the maximum degree of the graph induced by Vi is at most di for each i∈{1,...,r} . For a given pair (g,d1) , the question of determining the minimum d2=d2(g,d1) such that planar graphs with girth at least g are (d1,d2) ‐colorable has attracted much interest. The finiteness of d2(g,d1) was known for all cases except when (g,d1)=(5,1) . Montassier and Ochem explicitly asked if d2(5, 1) is finite. We answer this question in the affirmative with d2(5,1)≤10 ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K=K(γ) where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.