färgantal

Färgantalet i en graf G, vanligt betecknat χ(G), är det minsta antalet färger som krävs för att färga noderna så att två grannar inte har samma färg. En sådan färgning kallas en korrekt färgning.

Exempel: En väg är bipartit och χ(G) är 2 om grafen har minst en kant, medan en ensam nod utan kant har χ = 1. En triangel har χ = 3. Generellt gäller ω(G) ≤ χ(G) ≤ Δ(G) + 1, där ω är klique-tal och Δ är grafens maximala grad.

Särskilda klasser: plana grafer har χ(G) ≤ 4 (fyrfärgssatsen). För bipartita grafer är χ(G) = 2 eller 1 om det inte finns några kanter. För fullständiga grafer K_n är χ(G) = n.

Beräkning: att avgöra χ(G) är vanligtvis NP-svårt; beslutversionen “är χ(G) ≤ k?” är NP-fullständig. Därför används ofta heuristiker såsom greedy-färgning eller DSATUR, samt exakta metoder som backtracking för små grafer. Den relaterade färgpolynomen P_G(k) räknar antalet giltiga färgningar med k färger; χ(G) är det minsta k för vilket P_G(k) > 0.

Användningar: färgantalet används inom schemaläggning, registerallokering i kompilatorer och frekvensplanering.