A NOTE ON THE NP-COMPLETENESS OF THE PRECOLORING EXTENSION COLORING PROBLEM IN TRIANGLE FREE PLANAR GRAPHS

摘要

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V,E) and k pairwise disjoint subsets V_0,..., V_(k-1) of V, if there exists a (vertex) coloring S = (S_0,...,S_(k-1)) of G such that V_i is contained in S_i, for all i = 0,...,k - 1. In this note, we show that the precoloring extension coloring problem is NP-complete in triangle free planar graphs with maximum degree 4.