Precoloring extension involving pairs of vertices of small distance,
Precoloring extension involving pairs of vertices of small distance,
复制标题
涉及小距离顶点对的预着色扩展，
DOI：
10.1016/j.dam.2013.10.012
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Akira Sato and Kazuki Sano
中科院分区：
文献类型：
--
作者：
Chihoko Ojima;Akira Sato and Kazuki Sano
在这篇文章中，我们考虑在某些顶点已经着色的假设下的图的着色。设G是r-可染图，P⊂V(G)。Albertson(1998)证明了：如果P中的每一对顶点都至少有四个距离，则G[P]的每一个(r+1)-着色都可以扩展为G的一个(r+1)-着色，其中G[P]是由P诱导的子图。本文允许P有至多三个距离的顶点对，并研究了这样的顶点对的数目如何影响我们扩展G[P]的着色所需的色数。我们还研究了距离至多两个顶点对的影响，推广了Albertson和Moore(1999)的结果。
In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let G be an r-colorable graph and let P⊂ V (G). Albertson (1998) has proved that if every pair of vertices in P has distance at least four, then every (r+ 1)-coloring of G [P] can be extended to an (r+ 1)-coloring of G, where G [P] is the subgraph of G induced by P. In this paper, we allow P to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of G [P]. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore (1999).