Brooks tétele a gráfelmélet állítása, amely kapcsolatot hoz létre a gráf maximális foka és kromatikus száma között . E tétel szerint egy összefüggő gráf csúcsai, amelyekben minden csúcsnak legfeljebb ∆ szomszédja van , összesen ∆ színnel színezhetők , kivéve két esetet - a teljes gráfokat és a páratlan hosszúságú ciklusokat , amelyekhez ∆ + 1 szín szükséges.
A tétel nevét R. Leonard Brooksról kapta , aki 1941 -ben publikálta a tétel bizonyítását . A Brooks-tételben meghatározott számú színt használó színezést néha Brooks színezésnek vagy Δ - színezésnek nevezik .
Egy összefüggő irányítatlan G gráf esetén, amelynek maximális foka Δ , G kromatikus száma legfeljebb Δ , hacsak G nem klikk vagy páratlan ciklus. Ezekben az esetekben a kromatikus szám Δ + 1 .
Lovász László 1975 egyszerűsített bizonyítást ad Brooks tételére [1] . Ha a gráf nem bikapcsolt , akkor a bikapcsolt komponensei egyenként színezhetők, majd a színezések kombinálhatók. Ha a gráf tartalmaz egy v csúcsot , amelynek foka kisebb , mint ∆ , akkor a mohó színező algoritmus , amely a csúcsokat v -től való távolság szerint színezi (a távoliakat először, a közelieket utoljára), maximum ∆ színt használ [2] . Így a legnehezebben bizonyítható esetek a kétszeresen összefüggő Δ - szabályos gráfok, amelyeknél Δ ≥ 3 . Lovas megmutatja, hogy lehetséges olyan átívelő fát találni, ahol a v gyökér u és w nem szomszédos szomszédjai a fa levelei. Rendeljen egy (bármilyen) színt az u és w csúcsokhoz . Egy mohó algoritmus, amely u -tól és w -től indul, és átmegy a fedőfa többi részén (a gyökértől a levelekig felmászik), maximum Δ színeket használ. Ha a v kivételével minden csúcs színezett, akkor színezetlen szülője van, így a már kiszínezett színek nem használhatják az összes szabad színt, mivel v két szomszédja ( u és w ) ugyanazt a színt osztja. Színezd ki magát a v csúcsot a nem használt színnel .
A tétel egy általánosabb változata az előírt színezésre vonatkozik - adott egy összekapcsolt irányítatlan gráf maximális Δ fokával , amely nem egy klikk és nem páratlan hosszúságú ciklus, és egy Δ színek listája minden csúcshoz, kiválaszthatja a színét minden csúcsot a listából, hogy ne legyen két szomszédos csúcsnak egy színe. Más szavakkal, egy összekapcsolt irányítatlan gráf előírt kromatikus száma soha nem haladja meg a Δ -t, hacsak G nem egy klikk vagy egy páratlan hosszúságú ciklus. A tételt Vizing ( Vizing 1976 ) bizonyította.
Bizonyos típusú grafikonokhoz még kevesebb Δ színre van szükség. Reed ( Reed 1999 ) kimutatta, hogy a Δ - 1 színek akkor és csak akkor elegendőek, ha a gráf nem tartalmaz Δ -kliket, de Δ - nek elég nagynak kell lennie. Háromszög nélküli gráfokhoz , valamint a gráfok egy általánosabb osztályához, amelyben a csúcskörnyezetek kellően ritkák, az O (Δ/log Δ) színek elegendőek. [3] .
A gráfok mértéke egy másik színezési él felső határának becslésénél is megjelenik . Viizing tétele kimondja, hogy a kromatikus index nem haladja meg a Δ + 1 értéket . Brooks tételének kiterjesztését a teljes színezésre , amely szerint a teljes kromatikus szám nem haladja meg a Δ + 2 -t, Behzad és Viizing sejtésként javasolta. A Hajnal-Szemeredi egységes színezési tétel kimondja, hogy bármely gráfnak van olyan (Δ + 1) -színezése, hogy két különböző színű csúcsok száma legfeljebb eggyel tér el.
A Δ fokú gráf Δ -színezése, vagy akár egy előírt Δ -színezése megtalálható lineáris időben. [4] Hatékony algoritmusok ismertek a Brooks színezés megtalálására párhuzamos és elosztott számítási környezetekben [5] .