Kromatiskt tal

Kromatiskt tal är ett begrepp inom grafteorin i matematiken. Det kromatiska talet för en graf G, betecknat ${\displaystyle \gamma (G)}$, är det tal för en graf G som beskriver det minsta antalet färger som behövs för att färglägga grafen G. Vad som menas med att färglägga en graf kan tyckas oklart. I detta fallet kan man tänka sig ett antal hörn eller punkter som, på olika sätt, kombineras ihop med andra hörn. Detta görs genom att man drar linjer från ett hörn till ett annat. Principen går sedan ut på att om två hörn är i kontakt med varandra via en linje, får de inte ha samma färg. Med andra ord är det alltså hörnen man färgar och mellan hörnen dras linjer. Dessutom tillåts inte loopar, vilket betyder att en linje inte får återknytas till där den från början kom ifrån. Då det är omöjligt att tänka sig vilka färger hörnen i så fall skulle ha.