Siłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.dam.2009.03.008
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2009
