The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree - Publication - Bridge of Knowledge

Search

The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree

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

Cite as

Full text

full text is not available in portal

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 110 times

Recommended for you

Meta Tags