En grådig farvning i grafteori er en toppunktfarvning af en urettet graf skabt af en grådig algoritme , der krydser grafens hjørner i en foruddefineret rækkefølge og tildeler hvert toppunkt den første tilgængelige farve. Grådige algoritmer producerer generelt ikke det mindst mulige antal farver, men de bruges i matematik som en teknik til at bevise andre farveresultater og i computerprogrammer til at producere farvestoffer med et lille antal farver.
Kronen ( fuldstændig todelt graf K n , n med fjernede kanter af en perfekt matchning ) er et særligt dårligt tilfælde for den grådige algoritme - hvis to hjørner, der tilhører den fjernede kant fra matchningen, er placeret i en række i sekvensen af hjørner, den grådige algoritme bruger n farver, mens det optimale tal for sådan en graf er to farver. Der findes også grafer, for hvilke med stor sandsynlighed vil en tilfældigt valgt sekvens af hjørner føre til brug af et antal farver, der er væsentligt større end det minimum, der kræves [1] . Derfor er det meget vigtigt at omhyggeligt vælge den rækkefølge, hvori hjørnerne krydses af den grådige algoritme.
Givet en graf G og et tal k , er det et NP-komplet problem at bestemme, om der er en rækkefølge af hjørner i G , der får den grådige algoritme til at bruge k eller flere farver. Det betyder især, at det er svært at finde det værste tilfælde for grafen G [2] .
Enhver grafs hjørner kan altid ordnes på en sådan måde, at den grådige algoritme giver den optimale farve. Så for enhver optimal farvning omnummererer vi først (i faldende rækkefølge) hjørnerne fra det mindste sæt af identisk farvede hjørner. Så omnummererer vi det næststørste sæt, og så videre. Hvis vi nu anvender en grådig algoritme med denne rækkefølge af hjørner, vil den resulterende farvning være optimal. Mere strengt, for grafer, der har en perfekt rækkefølge (denne familie omfatter akkordgrafer , sammenlignelighedsgrafer og afstandsarvede grafer ), er der en rækkefølge, der er optimal både for selve grafen og for alle dens genererede undergrafer [3] . At finde denne optimale rækkefølge for en vilkårlig graf er imidlertid et NP-komplet problem (om ikke andet fordi dets løsning kan bruges til at opnå en optimal graffarvning, det vil sige et NP-komplet problem), og at bestemme, om en perfekt rækkefølge af toppunkter findes i en graf er også et NP-komplet problem [4] . Af denne grund bruges heuristiske algoritmer til at farve grafen for at reducere antallet af farver, selvom de ikke giver det optimale antal farver.
Normalt, for at sortere hjørnerne for den grådige algoritme, skal du vælge toppunktet v med minimumsgraden , bestille de resterende hjørner og sætte v i slutningen af listen. Hvis en undergraf af G indeholder hjørner med højst grad d , så bruger den grådige farvelægningsalgoritme maksimalt d + 1 farver for denne rækkefølge af hjørner [5] . Den mindste af d kaldes normalt grafens degeneration .
For en graf med maksimal grad Δ bruger enhver grådig algoritme maksimalt Δ + 1 farver. Brooks' sætning siger, at med to undtagelser ( kliker og ulige cyklusser ), behøver en farve højst Δ farver. Et bevis på Brooks' sætning bruger en toppunktsrækkefølge, hvor de første to toppunkter støder op til det endelige toppunkt, men ikke støder op til hinanden. En sådan sekvens har for hvert toppunkt mindst et tidligere toppunkt, der hører til nabolaget. For en sekvens af hjørner med disse egenskaber bruger den grådige algoritme maksimalt Δ - farver [6] .
Det er muligt at konstruere en grådig algoritme, hvor hjørnerne af en given graf er farvet i en forudbestemt rækkefølge, men hvor farven ikke nødvendigvis er valgt fra den første tilgængelige farve. Tilgange med online-algoritmer er blevet undersøgt som en alternativ farvevalgsstrategi . I problemet med onlinefarvning af en graf, føres grafens hjørner til farvealgoritmen sekventielt, én ad gangen, i en vilkårlig rækkefølge. Algoritmen skal vælge farven på hvert toppunkt udelukkende baseret på farverne og tilgrænsende af allerede behandlede toppunkter. I denne sammenhæng måles kvaliteten af en farvevalgsstrategi ved konkurrenceforholdet , forholdet mellem antallet af anvendte farver og det optimale antal farver i en graffarvning.
Hvis der ikke er givet andre begrænsninger på grafen, er det optimale konkurrenceforhold kun lidt sublineært [7] . For intervalgrafer er en konstant [8] dog mulig som konkurrenceforhold , mens der for todelte og sparsomme grafer kan opnås et logaritmisk forhold [9] . For sparsomme grafer giver den sædvanlige strategi med at vælge den første tilgængelige farve desuden dette estimat, og det kan påvises, at dette estimat er lavere for konkurrenceforholdet for enhver online farvealgoritme [9] .