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
2006Journal name
Foundations of Computing and Decision SciencesVolume
31Number
2Publisher
Poznań University of Technology
Pages
169-174
Metadata
Show full item recordAbstract (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 combinatoireRelated items
Showing items related by title and author.
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié
-
Lacroix, Mathieu; Mahjoub, Ali Ridha; Martin, Sébastien; Picouleau, Christophe (2012) Article accepté pour publication ou publié
-
Monnot, Jérôme (2008) Article accepté pour publication ou publié
-
Monnot, Jérôme (2007) Document de travail / Working paper
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012) Communication / Conférence