Brooks' teorem er et udsagn i grafteori, der etablerer en sammenhæng mellem den maksimale grad af en graf og dens kromatiske tal . Ifølge denne sætning kan toppunkterne i en sammenhængende graf, hvor alle toppunkter højst har ∆ - naboer, farves med ∆ -farver i alt, bortset fra to tilfælde - komplette grafer og cyklusser af ulige længder, som kræver ∆ + 1 farver.
Sætningen er opkaldt efter R. Leonard Brooks , som offentliggjorde beviset for sætningen i 1941 . En farvelægning, der bruger det antal farver, der er angivet i Brooks' sætning, kaldes undertiden en Brooks-farve eller Δ - farvning .
For en forbundet urettet graf G med maksimal grad Δ er det kromatiske antal af G højst Δ , medmindre G er en klike eller en ulige cyklus. I disse tilfælde er det kromatiske tal Δ + 1 .
László Lovász 1975 giver et forenklet bevis for Brooks' sætning [1] . Hvis grafen ikke er biforbundet , kan dens biforbundne komponenter farves individuelt, og derefter kan farvestofferne kombineres. Hvis grafen indeholder et toppunkt v med grad mindre end ∆ , så bruger den grådige farvealgoritme , som farver toppunkter i henhold til afstanden fra v (fjerne først, tæt på dem sidst), maksimalt ∆ farver [2] . De sværeste tilfælde at bevise er således dobbeltforbundne Δ - regulære grafer med Δ ≥ 3 . Lovas viser, at det er muligt at finde et spændingstræ, således at nogle ikke-tilstødende naboer u og w af roden v er blade af træet. Tildel en (en hvilken som helst) farve til hjørnerne u og w . En grådig algoritme, der starter ved u og w og går gennem resten af spændingstræet (klatring fra roden til bladene) bruger maksimalt Δ - farver. Når alle andre hjørner end v er farvede, har de en ufarvet forælder, så de allerede farvede farver kan ikke bruge alle de frie farver, da vs to naboer ( u og w ) deler samme farve. Farv selve toppunktet v i den ubrugte farve .
En mere generel version af sætningen refererer til en foreskrevet farve - givet en sammenhængende urettet graf med maksimal grad Δ , der hverken er en klike eller en cyklus af ulige længde, og en liste over Δ farver for hvert toppunkt, kan du vælge farven på hvert knudepunkt fra listen, så ikke to tilstødende spidser ikke har én farve. Med andre ord overstiger det foreskrevne kromatiske tal for en forbundet urettet graf aldrig Δ , medmindre G er en klike eller en cyklus med ulige længde. Sætningen blev bevist af Vizing ( Vizing 1976 ).
For nogle typer grafer er der brug for endnu færre Δ- farver. Reed ( Reed 1999 ) viste, at Δ − 1 farver er tilstrækkelige, hvis og kun hvis grafen ikke indeholder en Δ -klik, men Δ skal være stor nok. For trekantfrie grafer såvel som for en mere generel klasse af grafer, hvor toppunktkvarterer er tilstrækkeligt sparsomme, er O (Δ/log Δ) farver tilstrækkeligt. [3] .
Graden af grafer vises også, når man estimerer den øvre grænse for en anden type farvekant . Vizings teorem siger, at det kromatiske indeks ikke overstiger Δ + 1 . En udvidelse af Brooks' teorem til total farvning , der angiver, at det samlede kromatiske tal ikke overstiger Δ + 2 , blev foreslået af Behzad og Vizing som en formodning. Hajnal-Szemeredis ensartede farvesætning siger, at enhver graf har en (Δ + 1) -farvning, således at antallet af hjørner af to forskellige farver højst afviger med én.
En Δ -farvning, eller endda en foreskrevet Δ -farvning, af en graf med grad Δ kan findes i lineær tid. [4] Effektive algoritmer er kendt for at finde Brooks-farvningen i parallelle og distribuerede computermiljøer [5] .