Nenásytné zbarvení v teorii grafů je zbarvení vrcholů neorientovaného grafu vytvořené pomocí žravého algoritmu , který prochází vrcholy grafu v nějaké předem definované sekvenci a přiřazuje každému vrcholu první dostupnou barvu. Chamtivé algoritmy obecně nevytvářejí minimální možný počet barev, ale používají se v matematice jako technika pro dokazování jiných výsledků zbarvení a v počítačových programech pro vytváření zbarvení s malým počtem barev.
Koruna ( kompletní bipartitní graf K n , n s odstraněnými hranami dokonalé shody ) je zvláště špatný případ pro chamtivý algoritmus — pokud jsou dva vrcholy patřící k odstraněné hraně z párování umístěny v řadě v posloupnosti vrcholů, chamtivý algoritmus používá n barev, zatímco optimální počet pro takový graf jsou dvě barvy. Existují i grafy, u kterých s vysokou pravděpodobností náhodně zvolená posloupnost vrcholů povede k použití množství barev, které je výrazně větší než minimální požadované [1] . Je tedy velmi důležité pečlivě zvolit posloupnost, ve které jsou vrcholy procházeny chamtivým algoritmem.
Je- li dán graf G a číslo k , určit, zda existuje pořadí vrcholů v G , které způsobuje, že chamtivý algoritmus používá k nebo více barev, je NP-úplný problém. Zejména to znamená, že je obtížné najít nejhorší případ pro graf G [2] .
Vrcholy libovolného grafu lze vždy uspořádat tak, aby chamtivý algoritmus poskytoval optimální vybarvení. Pro jakékoli optimální vybarvení tedy přečíslujeme nejprve (v sestupném pořadí) vrcholy z nejmenší sady stejně barevných vrcholů. Poté přečíslujeme druhou největší množinu a tak dále. Pokud nyní použijeme chamtivý algoritmus s tímto pořadím vrcholů, bude výsledné zbarvení optimální. Přesněji řečeno, pro grafy, které mají dokonalé uspořádání (tato rodina zahrnuje akordické grafy , grafy srovnatelnosti a grafy zděděné vzdáleností ), existuje pořadí, které je optimální jak pro samotný graf, tak pro všechny jeho generované podgrafy [3] . Nalezení tohoto optimálního pořadí pro libovolný graf je však NP-úplný problém (už jen proto, že jeho řešení lze použít k získání optimálního zbarvení grafu, tedy NP-úplný problém), a určení, zda dokonalé uspořádání vrcholů existuje v grafu je také NP-úplný problém [4] . Z tohoto důvodu se k obarvení grafu používají heuristické algoritmy, aby se snížil počet barev, i když neposkytují optimální počet barev.
Obvykle, chcete-li seřadit vrcholy pro chamtivý algoritmus, vyberte vrchol v s minimálním stupněm , seřaďte zbývající vrcholy a vložte v na konec seznamu. Pokud kterýkoli podgraf G obsahuje vrcholy se stupněm nejvýše d , pak algoritmus žravého barvení používá maximálně d + 1 barev pro toto pořadí vrcholů [5] . Nejmenší z d se obvykle nazývá degenerace grafu.
Pro graf s maximálním stupněm Δ používá jakýkoli chamtivý algoritmus maximálně Δ + 1 barvy. Brooksův teorém říká, že až na dvě výjimky ( kliky a liché cykly ) zbarvení potřebuje maximálně Δ barev. Jeden důkaz Brooksova teorému používá uspořádání vrcholů, kde první dva vrcholy sousedí s konečným vrcholem, ale nesousedí spolu. Taková posloupnost má pro každý vrchol alespoň jeden předchozí vrchol patřící do okolí. Pro posloupnost vrcholů s těmito vlastnostmi používá greedy algoritmus maximálně Δ barev [6] .
Je možné zkonstruovat chamtivý algoritmus, ve kterém jsou vrcholy daného grafu vybarveny v předem určeném pořadí, ale ve kterém barva nemusí být nutně vybrána z první dostupné barvy. Přístupy s online algoritmy byly studovány jako alternativní strategie výběru barev . V problému online barvení grafu jsou vrcholy grafu přiváděny do barvícího algoritmu postupně, jeden po druhém, v libovolném pořadí. Algoritmus musí vybrat barvu každého vrcholu pouze na základě barev a přilehlosti již zpracovaných vrcholů. V této souvislosti je kvalita strategie výběru barev měřena konkurenčním poměrem , poměrem počtu použitých barev k optimálnímu počtu barev v obarvení grafu.
Nejsou-li v grafu uvedena žádná další omezení, je optimální poměr konkurence pouze mírně sublineární [7] . Pro intervalové grafy je však možná konstanta [8] jako konkurenční poměr , zatímco pro bipartitní a řídké grafy lze získat logaritmický poměr [9] . Navíc, pro řídké grafy, obvyklá strategie výběru první dostupné barvy poskytuje tento odhad a lze ukázat, že tento odhad je nižší pro konkurenční poměr jakéhokoli online barvícího algoritmu [9] .