Thumbnail - Request a copy

A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

Monnot, Jérôme (2006), A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs, Foundations of Computing and Decision Sciences, 31, 2, p. 169-174

Type
Article accepté pour publication ou publié
Date
2006
Journal name
Foundations of Computing and Decision Sciences
Volume
31
Number
2
Publisher
Poznań University of Technology
Pages
169-174
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Abstract (EN)
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.
Subjects / Keywords
Optimisation combinatoire