Résumé en anglais

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V, E) and k pairwise disjoint subsets V0,...,Vk-1 of V, if there exists a (vertex) coloring S = (S0,...,Sk-1) of G such that Vi ⊆ Si, 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.