Precoloring extension involving pairs of vertices of small distance

Chihoko Ojima, Akira Saito, Kazuki Sano

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\subset V(G)$. Albertson [J.\…