färgmängd

Färgmängd är inom matematiken termen för en mängd färger som används när man färglägger objekt i en given struktur. Ofta talar man om en färgpalett eller ett färgschema som är tillgängligt för färgläggningen av exempelvis grafer, ytor i planet eller andra combinatoriska objekt. En färgläggning är en funktion som tilldelar varje objekt i uppsättningen en färg från färgmängden.

Om reglerna kräver att angränsande objekt inte får samma färg, kallas färgläggningen proper. Den minsta storleken på en färgmängd som möjliggör en sådan färgläggning kallas färgantalet eller kromatiska talet hos strukturen; i grafteori används ofta termen kromatiska talet. För planar graf gäller fyrfärgssatsen: planar graf kan färgläggas med högst fyra färger.

Färgmängden kan också variera per objekt i problem som listfärgning, där varje objekt har en specifik lista över färger som får användas. Andra variationer inkluderar krav på jämn fördelning av färger eller färgning av kanter i stället för noder. Begreppet färgmängd är centralt i problem som kartfärgning, schemaläggning och resursallokering, där man vill minimera antalet färger eller resursbegränsningar under givna regler.

Se även: färgläggning, kromatiskt tal, fyrfärgssatsen, listfärgning.