En girig färgning i grafteori är en vertexfärgning av en oriktad graf skapad av en girig algoritm som korsar grafens hörn i någon fördefinierad sekvens och tilldelar varje vertex den första tillgängliga färgen . Giriga algoritmer producerar i allmänhet inte minsta möjliga antal färger, men de används i matematik som en teknik för att bevisa andra färgningsresultat och i datorprogram för att producera färger med ett litet antal färger.
Kronan ( komplett tvådelad graf K n , n med borttagna kanter av en perfekt matchning ) är ett särskilt dåligt fall för den giriga algoritmen - om två hörn som hör till den borttagna kanten från matchningen placeras i rad i sekvensen av hörn, den giriga algoritmen använder n färger, medan det optimala talet för en sådan graf är två färger. Det finns också grafer för vilka, med stor sannolikhet, en slumpmässigt vald sekvens av hörn kommer att leda till användningen av ett antal färger som är betydligt större än det minimum som krävs [1] . Därför är det mycket viktigt att noggrant välja sekvensen där hörnen korsas av den giriga algoritmen.
Givet en graf G och ett tal k , är det ett NP-komplett problem att avgöra om det finns en ordning av hörn i G som gör att den giriga algoritmen använder k eller fler färger. Framför allt innebär detta att det är svårt att hitta det värsta fallet för grafen G [2] .
Topppunkterna i en graf kan alltid ordnas på ett sådant sätt att den giriga algoritmen ger den optimala färgen. Så, för en optimal färgning, numrerar vi först (i fallande ordning) topparna från den minsta uppsättningen av identiskt färgade hörn. Sedan numrerar vi om den näst största uppsättningen och så vidare. Om vi nu tillämpar en girig algoritm med denna ordning av hörn, blir den resulterande färgningen optimal. Mer strikt, för grafer som har en perfekt ordning (denna familj inkluderar ackordsgrafer , jämförbarhetsgrafer och avståndsärvda grafer ), finns det en ordning som är optimal både för själva grafen och för alla dess genererade subgrafer [3] . Att hitta denna optimala ordning för en godtycklig graf är dock ett NP-komplett problem (om så bara för att dess lösning kan användas för att erhålla en optimal graffärgning, det vill säga ett NP-komplett problem), och att avgöra om en perfekt ordning av hörn finns i en graf är också ett NP-komplett problem [4] . Av denna anledning används heuristiska algoritmer för att färga grafen för att minska antalet färger, även om de inte ger det optimala antalet färger.
Vanligtvis, för att ordna hörnen för den giriga algoritmen, välj hörn v med minsta graden , ordna de återstående hörnen och sätt v i slutet av listan. Om någon subgraf av G innehåller hörn med högst grad d , så använder den giriga färgningsalgoritmen maximalt d + 1 färger för denna ordning av hörn [5] . Den minsta av d brukar kallas grafens degeneration .
För en graf med maximal grad Δ använder alla giriga algoritmer maximalt Δ + 1 färger. Brooks teorem säger att, med två undantag ( klickar och udda cykler ), behöver en färgning högst Δ- färger. Ett bevis på Brooks teorem använder en vertexordning där de två första hörnen ligger intill den slutliga vertexen, men inte intill varandra. En sådan sekvens har för varje hörn minst en tidigare hörn som hör till grannskapet. För en sekvens av hörn med dessa egenskaper använder den giriga algoritmen maximalt Δ- färger [6] .
Det är möjligt att konstruera en girig algoritm där hörnen i en given graf är färgade i en förutbestämd sekvens, men där färgen inte nödvändigtvis väljs från den första tillgängliga färgen. Tillvägagångssätt med onlinealgoritmer har studerats som en alternativ färgvalsstrategi . I problemet med onlinefärgning av en graf matas grafens hörn till färgningsalgoritmen sekventiellt, en i taget, i en godtycklig ordning. Algoritmen måste välja färgen på varje vertex baserat endast på färgerna och närliggande till redan bearbetade hörn. I detta sammanhang mäts kvaliteten på en färgvalsstrategi genom konkurrensförhållandet , förhållandet mellan antalet använda färger och det optimala antalet färger i en graffärgning.
Om inga andra begränsningar på grafen anges är det optimala konkurrensförhållandet endast något sublinjärt [7] . Men för intervallgrafer är en konstant [8] möjlig som ett konkurrensförhållande , medan för tvådelade och glesa grafer kan ett logaritmiskt förhållande [9] erhållas . Dessutom, för glesa grafer, ger den vanliga strategin att välja den första tillgängliga färgen denna uppskattning, och det kan visas att denna uppskattning är lägre för konkurrensförhållandet för någon online-färgningsalgoritm [9] .