Search
Abstract
Rozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
Authors (3)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
International Journal of Pure and Applied Mathematics
no. 27,
pages 377 - 389,
ISSN: 1311-8080 - Language:
- English
- Publication year:
- 2006
- Bibliographic description:
- Furmańczyk H., Giaro K., Kubale M.: Equitable 4-coloring of cacti and edge-cacti in polynomial time// International Journal of Pure and Applied Mathematics. -Vol. 27., iss. 3 (2006), s.377-389
- Verified by:
- Gdańsk University of Technology
seen 128 times