Knudefarvning

Der er ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive kilder til de påstande, der fremføres. Hvis ikke der tilføjes kilder, vil artiklen muligvis blive slettet (juni 2020) (Lær hvordan og hvornår man kan fjerne denne skabelonbesked)

Knudefarvning af en graf drejer sig om tildeling af farver til grafens knuder, på en sådan måde, at vilkårlige to kantforbundne knuder har forskellige farver – dette kaldes en egentlig knudefarvning. Det er klart, at der for en vilkårlig graf findes egentlige knudefarvninger, nemlig ved at tildele hver knude en separat farve. Farverne specificeres ved en afbildning φ : V → F , hvor F kan eksempelvis være et afsnit af de naturlige tal. φ(v) er den til v ∈ V givne farve, hvor V er mængden af knuder i grafen. Det mindste antal farver i en egentlig knudefarvning af en graf G kaldes det kromatiske tal, eller det knudekromatiske tal, for G og det betegnes χ (G).

• De komplette grafer K_n har alle kromatisk tal χ(K_n) = n, hvor n er et naturligt tal. Da vilkårlige forskellige knuder i K_n er kantforbundne, skal hver knude derfor have sin egen farve.
• En graf G har en tom kantmængde, hvis den kan knudefarves med én farve; dvs. χ(G) = 1. Sådan en graf består kun af en knude.
• En kreds C_n bestående af et lige antal knuder (og kanter) har kromatisk tal 2. Farvningen af grafen fås ved at lade de 2 farver alternere langs kredsen, dvs. bruge farverne skiftevis (se figuren). Hvorimod en kreds C_n af et ulige antal knuder (og kanter) har kromatisk tal 3. Forsøger man at farve grafen ved at lade 2 farver alternere langs kredsen, vil man opdage at den sidste knude der skal farves er forbundet med to kanter, hvis endeknuder har forskellige farver. Dvs. denne knude skal farves med en tredje farve ifølge definitionen af en egentlig kantfarvning.

• Kantfarvning