Graafi värvimise uurija

Kromaatiline arv χ(G) on minimaalne värvide arv, mille korral ükski serv ei ühenda kahte samavärvilist tippu. Selle täpne leidmine on NP-raske — parim üldine garantii jääb kliki alampiiri (iga suurusega k klikk nõuab vähemalt k värvi) ja ahne ülempiiri vahele (Welsh-Powelli värvimine kahaneva astme järgi ei kasuta kunagi rohkem kui Δ+1 värvi, kus Δ on maksimaalne aste). Tasapinnaliste graafide jaoks — need, mida saab joonistada ilma servade ristumiseta — garanteerib neljavärviteoreem, et alati piisab 4 värvist; see tõestati esimest korda arvuti abil 1976. aastal ja on siiani üks vähestest olulistest teoreemidest, mis nõuab ammendavat arvutipõhist juhtumite kontrolli. Graafi värvimine on aluseks reaalsetele jaotusprobleemidele: registrite jaotamine kompilaatorites, eksamite ajakavastamine ja raadiosageduste jaotamine taanduvad kõik konfliktigraafi värvimisele.

Graafi värvimine taandub ühele reeglile: ükski serv ei tohi ühendada kaht sama värvi tippu ning värve tahad kasutada võimalikult vähe. See ainus tingimus otsustab kõik. Kasulik test: iga paarisarvulise pikkusega tsükkel saab hakkama 2 värviga, kuid iga paaritu pikkusega tsükkel vajab 3 — nii et kolmnurka (väikseimat paaritut tsüklit) ei saa kunagi 2 värviga värvida. Ehita mõlemad tööriistas ja jälgi konfliktide arvu.

Tippude värvimine ükshaaval, valides alati madalaima vaba värvi, tundub turvaline, kuid järjekord on äärmiselt oluline. Nn kroongraafide puhul — 2n tippu, mis vajavad vaid 2 värvi — sunnib pahatahtlik järjekord ahne meetodi kasutama hoopis n värvi. Selle halvim juht on tõkestamata, mistõttu tööriista automaatvärvimine järjestab tipud kahaneva astme järgi (Welsh-Powell), et selliseid lõkse vältida.