Färgbarhet

Färgbarhet är en egenskap där ett objekt kan tilldelas färger enligt givna regler för att uppnå avsedda skillnader. Inom grafteori handlar färgbarhet om att färglägga hörn eller regioner så att vissa krav uppfylls, till exempel att angränsande element får olika färger.

En graf är k-färgbar om dess hörn kan färgläggas med högst k färger så att varje par av närliggande hörn får olika färger. Den minsta siffra k som möjliggör en sådan färgläggning kallas grafens kromatiska tal, χ(G). En korrekt färgläggning kallas ibland en proper färgläggning, och färgningen är ofta mått på hur komplext strukturen är att färglägga.

Planar grafer är 4-färgbar enligt fyra färgläggningens sats. Kartor på en planet eller på en skals kartbilder kan därför färgläggas med fyra färger så att gränserna mellan olika länder inte sammanfaller. Utanför plana ytor studeras även färgbarheter för olika typer av objekt, som regioner i kartor, vilket i praktiken motsvarar regionfärgning.

Andra typer av färgbarhet inkluderar kantfärgbarhet, där kanter färgläggs så att intilliggande kanter får olika färger, samt listfärgbarhet där varje hörn har begränsade färgval. Det finns även begrepp som choosability och varierande färgläggningskrav beroende på kontext.

Komplexiteten varierar: beslutet om huruvida en graf är k-färgbar är NP-komplett för k ≥ 3, medan tvåfärgbarhet (bipartitet) kan avgöras i polynomtid. Färgbarhet används i praktiska tillämpningar som schemaläggning, frekvensplanering och registerallokering.