Search results for: DRZEWO WIELOKĄTOWE

• Equitable 4-coloring of cacti and edge-cacti in polynomial time

  Publication

  • H. Furmańczyk
  • K. Giaro
  • M. Kubale

  - International Journal of Pure and Applied Mathematics - Year 2006

  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.

  Full text to download in external service