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
Komplexitet: Beslutsproblemet att avgöra om en given graf är k-färgbar är NP-fullständigt för varje konstant k ≥
Algoritmer och klasser: Det finns exakta backtracking-algoritmer och heuristiker (t.ex. DSATUR) för färgningsproblem, samt polynomalgoritmer för
Användning och varianter: Färgning används inom schemaläggning, registerallokering, kartfärgning och radiografi. Varianter innefattar listfärgning, precoloring extension
Se även: graf, kromatiskt tal, bipartit graf, planar graf, Four Color Theorem.