Brooksin lause on graafiteorian lause, joka määrittää suhteen graafin maksimiasteen ja sen kromaattisen luvun välillä . Tämän lauseen mukaan yhdistetyn graafin kärjet, joissa kaikilla pisteillä on korkeintaan ∆ - naapureita, voidaan värjätä yhteensä ∆ -väreillä, paitsi kaksi tapausta - täydet graafit ja parittoman pituiset syklit , jotka vaativat ∆ + 1 väriä.
Lause on nimetty R. Leonard Brooksin mukaan, joka julkaisi lauseen todisteen vuonna 1941 . Brooksin lauseessa määritettyä värimäärää käyttävää värjäystä kutsutaan joskus Brooksin värjäykseksi tai Δ - väritykseksi .
Yhdistetylle suuntaamattomalle graafille G , jonka maksimiaste Δ , G : n kromaattinen luku on enintään Δ , ellei G ole klikki tai pariton jakso. Näissä tapauksissa kromaattinen luku on Δ + 1 .
László Lovász 1975 antaa yksinkertaistetun todisteen Brooksin lauseesta [1] . Jos kuvaaja ei ole kaksoiskytkentäinen , sen kaksikytketyt komponentit voidaan värjätä yksitellen ja sitten värit yhdistellä. Jos graafi sisältää pisteen v , jonka aste on pienempi kuin ∆ , niin ahne väritysalgoritmi , joka värjää kärjet etäisyyden v :stä mukaan (kaukaiset ensin, läheiset viimeisenä), käyttää enintään ∆ värejä [2] . Näin ollen vaikeimmin todistettavissa olevat tapaukset ovat kaksinkertaisesti kytketyt Δ -säännölliset graafit , joissa Δ ≥ 3 . Lovas osoittaa, että on mahdollista löytää virittävä puu siten, että jotkin juuren v eivät vierekkäiset naapurit u ja w ovat puun lehtiä. Määritä yksi (mikä tahansa) väri pisteisiin u ja w . Ahne algoritmi, joka alkaa u :sta ja w : stä ja käy läpi muun virittävän puun (kiipeämällä juuresta lehtiin), käyttää enintään Δ - värejä. Kun kaikki muut kärjet v :tä lukuun ottamatta ovat värillisiä, niillä on väritön vanhempi, joten jo värilliset värit eivät voi käyttää kaikkia vapaita värejä, koska v :n kahdella naapurilla ( u ja w ) on sama väri. Väritä itse vertex v käyttämättömällä värillä .
Lauseen yleisempi versio viittaa määrättyyn värjäykseen - kun otetaan huomioon kytketty suuntaamaton graafi, jonka suurin aste Δ ei ole klikki eikä pariton sykli, ja luettelo Δ -väreistä jokaiselle kärkipisteelle, voit valita värin. jokainen kärki listasta, jotta kahdella vierekkäisellä kärjellä ei ole yhtä väriä. Toisin sanoen yhdistetyn suuntaamattoman graafin määrätty kromaattinen luku ei koskaan ylitä arvoa Δ , ellei G ole parittoman pituinen klikki tai sykli. Lauseen todisti Vizing ( Vizing 1976 ).
Joillekin kaaviotyypeille tarvitaan vielä vähemmän Δ -värejä. Reed ( Reed 1999 ) osoitti, että Δ − 1 värit ovat riittäviä, jos ja vain jos graafi ei sisällä Δ -klikkiä, mutta Δ :n on oltava riittävän suuri. Kolmiottomille graafiille sekä yleisemmälle graafiluokalle, jossa pisteen lähialueet ovat riittävän harvat, O (Δ/log Δ) värit riittävät. [3] .
Graafisten aste näkyy myös estimoitaessa toisen tyyppisen väritysreunan ylärajaa . Visingin lause sanoo, että kromaattinen indeksi ei ylitä Δ + 1 . Behzad ja Vizing ehdottivat olettamukseksi Brooksin lauseen laajennuksen kokonaisvärjäykseen , jonka mukaan kromaattinen kokonaisluku ei ylitä arvoa Δ + 2 . Hajnal-Szemeredin yhtenäinen värityslause sanoo, että millä tahansa graafilla on (Δ + 1) -väritys siten, että kahden eri värin kärkien lukumäärä eroaa korkeintaan yhdellä.
Graafille, jonka aste on Δ , Δ -värjäys tai jopa määrätty Δ -väritys voidaan löytää lineaarisessa ajassa. [4] Tunnetaan tehokkaita algoritmeja Brooksin värityksen löytämiseen rinnakkaisissa ja hajautetuissa laskentaympäristöissä [5] .