Defective choosability of graphs in surfaces
Defective choosability of graphs in surfaces
复制标题
曲面中图形的可选择性有缺陷
DOI：
--
复制
发表时间：
2011
影响因子：
0.7
通讯作者：
D. R. Woodall
中科院分区：
文献类型：
--
作者：
D. R. Woodall
已知，如果G是一个可以在具有欧拉特征的曲面上画出无边相交的图，且k和d是正整数，使得k bbb3和d在k和上足够大，则G是(k;d) -可着色的；也就是说，G的顶点可以用k种颜色着色，这样每个顶点最多有d个与自己颜色相同的邻居。本文对d的已知下界作了简化，并证明了一个类似的结果
It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic �, and k and d are positive integers such that k > 3 and d is sufficiently large in terms of k and �, then G is (k;d) � -colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved f or