On (3, 1)*-Coloring of Plane Graphs
On (3, 1)*-Coloring of Plane Graphs
复制标题
DOI：
10.1137/06066093x
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
Baogang Xu
中科院分区：
文献类型：
--
作者：
Baogang Xu
给定正整数$k$和$d$，称图$G$是$(k，d)^*$-可染的，如果$G$的顶点可以用$k$颜色着色，使得每个顶点至多有$d$个邻居接受与其本身相同的颜色。设G是既不含相邻三角形也不含长为5的圈的平面图族，本文证明了它的每个图都是$(3，1)^*$-可染的。这一结果是尖锐的，因为存在非$(2，1)^*$-可染平面图，其中既没有长为5的三角形，也没有长为5的圈。作为推论，去掉匹配后，$G}$中的每个图都是3-可染的。这部分地解决了Borodin和Raspaud的一个猜想[J.Combin.理论系列。B，93(2003)，第17-27页]。
Given positive integers $k$ and $d$, a graph $G$ is said to be $(k,d)^*$-colorable if the vertices of $G$ can be colored with $k$ colors such that every vertex has at most $d$ neighbors receiving the same color as itself. Let ${\cal G}$ be the family of plane graphs with neither adjacent triangles nor cycles of length 5. It is proved in this paper that every graph in ${\cal G}$ is $(3,1)^*$-colorable. This result is sharp in the sense that there exist non-$(2,1)^*$-colorable plane graphs with neither triangles nor cycles of length 5. As a corollary, after removing a matching, every graph in ${\cal G}$ is 3-colorable. This provides a partial solution to a conjecture of Borodin and Raspaud [J. Combin. Theory Ser. B, 93 (2003), pp. 17-27].