$(1, k)$-coloring of graphs with girth at least $5$ on a surface
$(1, k)$-coloring of graphs with girth at least $5$ on a surface
复制标题
$(1, k)$-表面上周长至少为 $5$ 的图形的着色
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Geewon Suh
中科院分区：
文献类型：
--
作者：
Hojin Choi;Ilkyoo Choi;Jisu Jeong;Geewon Suh
图是$（d_1，.，d_r）$-可着色的，如果它的顶点集可以被划分为$r$个集合$V_1，...，V_r$使得由$V_i$诱导的图的最大度对于\{1，.，r\}$。对于给定的对$（g，d_1）$，确定最小值$d_2=d_2（g; d_1）$使得围长至少为$g$的平面图$（d_1，d_2）$-可染的问题引起了人们的极大兴趣。除了当$（g，d_1）=（5，1）$时，$d_2（g; d_1）$的有限性是已知的。Montassier和Ochem明确地询问了$d_2（5; 1）$是否是有限的。我们用$d_2（5; 1）\leq 10$肯定地回答了这个问题;也就是说，我们证明了所有围长至少为$5$的平面图都是$（1，10）$-可着色的。此外，我们的证明扩展到声明，对于任何表面$S$的欧拉亏格$\gamma$，存在$K=K（\gamma）$，其中周长至少为$5$的图是$（1，K）$-可着色的。另一方面，不存在有限k$，其中围长至少为5 $的平面图（因此可嵌入任何曲面）是$（0，k）$-可着色的。
A graph is $(d_1, ..., d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, ..., r\}$. For a given pair $(g, d_1)$, the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)\leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphs with girth at least $5$ 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 $5$ are $(0, k)$-colorable.