Zastępując jego oszacowaniem, otrzymuje się następujące oszacowanie liczby multichromatycznej: .
Nie są znane inne oszacowania w przypadku ogólnym.
Wartość dla szczególnych klas grafów Dla grafów dwudzielnych i doskonałych Dla grafów dwudzielnych znana jest dokładna wartość liczby multichromatycznej. Dla każdego ważonego grafu dwudzielnego zachodzi równość Lata Narayanan, Sunil. M. Shende: Static frequency assignment in cellular networks, Algorithmica 29, s. 396–409, 2001..
Powyższa równość jest prawdziwa także dla grafów doskonałychRichard Diestel: Graph theory II, Springer-Verlag, 2000..
Dla cykli Dla każdego ważonego cyklu o wierzchołkach z funkcją wagi zachodzi równość: .
Dla grafów planarnych Dla każdego grafu planarnego zachodzi nierówność Togni: Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes, Discrete mathematics & theoretical computer science 8(1), s. 159–172, 2006..
Zobacz też kolorowanie grafu liczba chromatyczna multikolorowanie grafu
Przypisy
Kategoria:Teoria grafów