Twierdzenie Brooksa
Twierdzenie Brooksa – w teorii grafów twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i liczbą chromatyczną w grafie. Nazwa twierdzenia została ustanowiona na cześć angielskiego matematyka Rowlanda Leonarda Brooksa, który opublikował jego dowód w 1941 roku.
Twierdzenie edytuj
Jeżeli graf G jest spójny i nieskierowany oraz nie jest grafem pełnym ani cyklem o nieparzystej długości, to liczba chromatyczna tego grafu jest nie większa niż maksymalny stopień wierzchołka Δ w tym grafie[1].
Jeżeli graf jest grafem pełnym lub cyklem o nieparzystej długości, to jego liczba chromatyczna wynosi [1]
Przypisy edytuj
- ↑ a b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 99. ISBN 0-387-95014-1.