Repozytorium publikacji - Politechnika Gdańska

W pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny dla wszystkich wartości ''p'' i ''q'', zamykając tym samym dwa problemy otwarte stawiane w literaturze.

Autorzy

• dr hab. inż. Robert Janczewski link otwiera się w nowej karcie ,
• dr inż. Adrian Kosowski link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie