Show simple item record

dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2010-01-13T12:11:04Z
dc.date.available2010-01-13T12:11:04Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2913
dc.language.isoenen
dc.subjectOptimisation combinatoireen
dc.subject.ddc003en
dc.titleA note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.en
dc.relation.isversionofjnlnameFoundations of Computing and Decision Sciences
dc.relation.isversionofjnlvol31en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages169-174en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPoznań University of Technologyen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record