Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872333 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chihoko Ojima, Akira Saito, Kazuki Sano,