Search
Abstract
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.
Citations
-
9
CrossRef
-
0
Web of Science
-
8
Scopus
Authors (3)
Cite as
Full text
download paper
downloaded 11 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.disc.2008.09.028
- License
- Copyright (2008 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE MATHEMATICS
no. 309,
pages 3270 - 3279,
ISSN: 0012-365X - Language:
- English
- Publication year:
- 2009
- Bibliographic description:
- Janczewski R., Kosowski A., Małafiejski M.: The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree // DISCRETE MATHEMATICS. -Vol. 309, (2009), s.3270-3279
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.disc.2008.09.028
- Verified by:
- Gdańsk University of Technology
seen 157 times