kfärgbar

K-färgbarhet (k-färgbar graf) är en egenskap hos en graf som beskriver om det går att färga grafens hörn med högst k färger så att intilliggande hörn får olika färger. Denna egenskap är samma sak som att grafens kromatiska tal χ(G) är mindre än eller lika med k. χ(G) är det minsta antalet färger som krävs för en giltig färgning av G.

Exempel och viktiga fall: En graf är 2-färgbar om och endast om den är bipartit; det vill säga grafen kan delas upp i två delmängder där varje kant går mellan delmängderna. En jämn cykel är 2-färgbar, medan en udda cykel kräver minst tre färger och därmed inte är 2-färgbar. Fullständiga grafer K_n kräver n färger. Enligt fyra färg-satsen är varje plan graf 4-färgbar. Generellt är svårighetsgraden olika beroende på k och grafens struktur.

Komplexitet och metoder: Att avgöra om en given graf är k-färgbar är NP-komplett för varje fast k ≥ 3. För k = 2 kan problemet lösas i polynom tid genom att kontrollera om grafen är bipartit (till exempel med BFS). Färgningsalgoritmer som greedy, DSATUR och andra heuristiska metoder används i praktiken för att hitta giltiga färgningar och att få övre gränser på χ(G). Det finns också variationer som listfärgning och jämn färgning som utökar begreppet.

Tillämpningar och sammanhang: Graffärgning används inom schemaläggning, frekvensplanering, kartfärgning och andra optimeringsproblem där man vill minimera antal färger eller resurser som behövs utan konflikt. Relaterade begrepp inkluderar kromatiskt tal, algoritmer för färgning och olika färgningsregler som kan göra problemet högre eller lägre i komplexitet beroende på underlag och restriktioner.