Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: triangle free planar graphs

Sortuj według:

Ogranicz wyniki do:

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

Monnot J.

Foundations of Computing and Decision Sciences

2006

Vol. 31, No. 2

169-173

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V,E] and k pairwise disjoint subsets Vo, ..., Vk-1 of V, if there exists a (vertex) coloring S = (So,...,Sk-i) of G such that Vi ⊇ Si, for all i = 0,...,k-1:— 1. In this note, we show that the precoloring extension coloring problem is NP-complete in triangle free planar graphs with maximum degree 4.