kfärgbarhet

K-färgbarhet, eller färgbarhet med k färger, är ett begrepp inom grafteori som beskriver om en graf G kan färgas så att närliggande hörn får olika färger och användningen inte överstiger k färger. En färgningsfunktion f: V(G) → {1,...,k} uppfyller kravet att f(u) ≠ f(v) när u och v är grannar. Den minsta k som uppfyller detta kallas grafens kromatiska tal, χ(G).

Exempelvis är en graf utan kanter 1-färgbar, och en graf är 2-färgbar om och endast om den är bipartit, det vill säga den innehåller inget udda cykellängd. Planar grafer är färgbara med högst fyra färger enligt Four Color Theorem, men beslutet om 3-färgbarhet för planar graf är NP-fullständigt i allmänhet.

Komplexitet: Beslutsproblemet att avgöra om en given graf är k-färgbar är NP-fullständigt för varje konstant k ≥ 3. För k = 1 är frågan trivial, och för k = 2 är problemet polynomtidigt (kan avgöras i linjär tid genom att testa bipartitet med BFS).

Algoritmer och klasser: Det finns exakta backtracking-algoritmer och heuristiker (t.ex. DSATUR) för färgningsproblem, samt polynomalgoritmer för vissa grafklasser som träd och vissa typer av sammanbindade intervallgrafar. Generellt blir färgningsproblem svårare med ökande k och komplexiteten varierar mellan graffamiljer.

Användning och varianter: Färgning används inom schemaläggning, registerallokering, kartfärgning och radiografi. Varianter innefattar listfärgning, precoloring extension och online-färgning.

Se även: graf, kromatiskt tal, bipartit graf, planar graf, Four Color Theorem.