Precoloring extension involving pairs of vertices of small distance

preprint2013arXivOpen access

Abstract

In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let GG be an rr-colorable graph and let P⊂V(G)P\subset V(G). Albertson [J.\ Combin.\ Theory Ser. B \textbf{73} (1998), 189--194] has proved that if every pair of vertices in PP have distance at least four, then every (r+1)(r+1)-coloring of G[P]G[P] can be extended to an (r+1)(r+1)-coloring of GG, where G[P]G[P] is the subgraph of GG induced by PP. In this paper, we allow PP 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]G[P]. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore [J.\ Combin.\ Theory Ser. B \textbf{77} (1999) 83--95].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.