A mohó színezés a gráfelméletben egy irányítatlan gráf csúcsszínezése , amelyet egy mohó algoritmus hoz létre, amely valamilyen előre meghatározott sorrendben bejárja a gráf csúcsait, és minden csúcshoz hozzárendeli az első elérhető színt. A mohó algoritmusok általában nem állítják elő a lehető legkisebb számú színt, de a matematikában használják más színezési eredmények bizonyítására, számítógépes programokban pedig kis számú színnel történő színezésre.
A korona ( K n , n teljes bipartit gráf tökéletes illeszkedés eltávolított éleivel ) különösen rossz eset a mohó algoritmus számára – ha az illesztésből eltávolított élhez tartozó két csúcsot egy sorba helyezzük a csúcsok sorozatában, a mohó algoritmus n színt használ, míg az optimális szám egy ilyen gráf esetében két szín. Vannak olyan gráfok is, amelyeknél nagy valószínűséggel egy véletlenszerűen kiválasztott csúcssorozat a minimálisan szükségesnél lényegesen nagyobb számú szín használatához vezet [1] . Ezért nagyon fontos, hogy gondosan válasszuk ki azt a sorozatot, amelyben a csúcsokat bejárja a mohó algoritmus.
Adott egy G gráf és egy k szám , annak meghatározása, hogy van-e olyan csúcssorrend G -ben , amely miatt a mohó algoritmus k vagy több színt használ, NP-teljes probléma. Ez különösen azt jelenti, hogy nehéz megtalálni a legrosszabb esetet a G [2] gráfra .
Bármely gráf csúcsai mindig úgy rendezhetők, hogy a mohó algoritmus az optimális színezést adja. Tehát bármilyen optimális színezéshez először újraszámozzuk (csökkenő sorrendben) a csúcsokat az azonos színű csúcsok legkisebb halmazából. Ezután újraszámozzuk a második legnagyobb halmazt, és így tovább. Ha most egy mohó algoritmust alkalmazunk ezzel a csúcsrenddel, akkor a kapott színezés optimális lesz. Pontosabban, a tökéletes sorrendű gráfok esetében (ebbe a családba tartoznak az akkordgráfok , az összehasonlíthatósági gráfok és a távolság öröklött gráfok ) van egy olyan sorrend, amely optimális mind magának a gráfnak, mind annak összes generált részgráfjának [3] . Ennek az optimális sorrendnek a megtalálása egy tetszőleges gráfhoz azonban NP-teljes probléma (már csak azért is, mert megoldásával optimális gráfszínt kaphatunk, azaz NP-teljes probléma), és annak meghatározása, hogy a csúcsok tökéletes sorrendje-e. létezik egy gráfban is egy NP-teljes probléma [4] . Emiatt heurisztikus algoritmusokat használnak a gráf színezésére a színek számának csökkentése érdekében, bár ezek nem adják meg az optimális színszámot.
Általában a mohó algoritmus csúcsainak rendezéséhez válassza ki a v csúcsot a minimális fokszámmal , rendezze a többi csúcsot, és tegye v -t a lista végére. Ha G bármely részgráfja legfeljebb d fokozatú csúcsokat tartalmaz , akkor a mohó színező algoritmus maximum d + 1 színt használ ehhez a csúcsrendhez [5] . A legkisebb d -t általában a gráf degeneráltságának nevezik.
Egy maximális Δ fokú gráf esetén bármely mohó algoritmus legfeljebb Δ + 1 színt használ. Brooks tétele kimondja, hogy két kivétellel ( klikk és páratlan ciklus ) egy színezéshez legfeljebb Δ színek szükségesek. Brooks tételének egyik bizonyítása olyan csúcsrendezést használ, ahol az első két csúcs szomszédos a végső csúcsgal, de nem szomszédos egymással. Egy ilyen sorozatnak minden csúcshoz legalább egy korábbi csúcsa van, amely a szomszédsághoz tartozik. Ezekkel a tulajdonságokkal rendelkező csúcsok sorozatához a mohó algoritmus legfeljebb Δ színt használ [6] .
Lehetőség van egy mohó algoritmus felépítésére, amelyben egy adott gráf csúcsait előre meghatározott sorrendben színezzük, de a színt nem feltétlenül az első elérhető színből választjuk. Az online algoritmusokkal történő megközelítéseket alternatív színkiválasztási stratégiaként tanulmányozták . A gráf online színezésének problémájában a gráf csúcsai egymás után, egyenként, tetszőleges sorrendben kerülnek a színező algoritmusba. Az algoritmusnak csak a már feldolgozott csúcsok színei és szomszédossága alapján kell kiválasztania az egyes csúcsok színét. Ebben az összefüggésben a színkiválasztási stratégia minőségét a versenyarány méri, amely a felhasznált színek számának és a grafikon színezésének optimális színszámának aránya.
Ha nem adunk meg más megkötést a grafikonon, akkor az optimális versenyarány csak kismértékben szublineáris [7] . Intervallumgráfok esetén azonban lehetséges egy [8] konstans versengési arányként , míg a kétrészes és ritka gráfok esetében logaritmikus arány [9] érhető el . Sőt, ritka gráfok esetén az első elérhető szín kiválasztásának szokásos stratégiája ezt a becslést adja, és kimutatható, hogy ez a becslés bármely online színező algoritmus versenyarányára alacsonyabb [9] .