Graffärgning

Graffärgning är ett begrepp inom grafteorin i matematiken, som beskriver en tilldelning av färger till antingen kanterna eller noderna uppfyllandet ett visst villkor. Om det är en färgläggning av noderna, kallad en nodfärgning, får inte två noder som har en kant mellan sig vara av samma färg. Om det är en färgläggning av kanterna så får två kanter som möts i en nod inte ha samma färg.

Formell definition

När man bara säger graffärgning är det oftast en nodfärgning som avses. Den definieras formellt som en funktion från noderna i grafen till någon mängd av "färger" (som t.ex. kan representeras av heltal) sådan att inga noder som är incidenta delar färg.

Kromatiskt polynom

För varje graf finns det ett polynom i k, kallat det kromatiska polynomet, som anger på hur många sätt man kan färglägga en graf med hjälp av k färger.

Fyrfärgsproblemet

Historiskt sett har det så kallade fyrfärgsproblemet varit en viktig inspirationskälla för studiet av graffärgningar.