• Rendezzük sorba csúcsainkat
• Az i-edik színezõ lépésben a sorrendben i-edik csúcshoz, v-hez színt rendelünk a következõ módon: a színek sorrendjében elsõ v szomszédai által fel nem vett színt kapja v.

Az algoritmus megértéséhez legjobb út egy példa végiggondolása.

Amíg van ki nem színezett csúcs addig ismételgessük a következõket:

• A még nem színezett csúcsok közül válasszunk ki egy v csúcsot.
• v-hez színt rendelünk a következõ módon: a színek sorrendjében elsõ v szomszédai által fel nem vett színt kapja v.

Az elsõ változat elõnye, hogy a csúcsok egy p sorbaállítása esetén egy egyértelmûen definiált mohó-kromatikus számot definiál: x_p(G), amely nyilván felülrõl becsli a kormatikus számot.

Tétel: Legyen G egy tetszõleges gráf és p csúcsainak egy tetszõleges sorrendje. Ekkor x_p(G)<₌D(G)+1, ahol D(G) a G gráf maximális fokszáma.

Bizonyítás: Tetszõleges csúcs színezésénél a tiltott színek száma felülrõl becsülhetõ a már színezett szomszédok számával, ami felülrõl becsülhetõ az aktuális csúcs fokszámával, ami felülrõl becsülhetõ D(G)-vel. Így a színezésnél minden színválasztásnál legfeljebb D(G) tiltott szín lehet, azaz D(G)+1 színû paletta elegendõ a színezéshez.

Példa: Legyen G az az egyszerû páros gráf, amely két színosztálya {x₁,x₂,...,x_n-1,x_n} és {y₁,y₂,...,y_n-1,y_n}, továbba x_i és y_j akkor és csak akkor van összekötve, ha i és j különbözik. Legyen p=x₁,y₁, x₂,y₂,..., x_n-1,y_n-1, x_n,y_n. Ekkor x_p=n, míg x(G)=2. Azaz p egy ``nagyon rossz'' sorrend.

Példa: Legyen G egy tetszõleges G gráf, amelyre x(G)=k. Színezzük ki csúcsait jól az 1,2,...,k színekkel (azaz optimálisan). Legyen p az a sorrendje csúcsainknak, amely a színeket követi. Azaz egy elsõ blokkban jönnek az 1 színû csúcsok, majd egy blokkban a 2 színû csúcsok ... Ekkor $x_p(G)=x(G)$. Valóban egyszerû meggondolni (a sorrendünket követõ teljes indukcióval bebizonyítani), hogy a mohó színezés sose ad nagyobb színt mint a kiinduló optimális színezés. Azaz p egy ``nagyon jó '' sorrend. Persze példánk gyakorlati értéke nulla a jó sorrendet egy optimáis színezés alapján adja meg, ami értéktelen eljárás.

Tanulság: Érdemes a mohó színezés sorrendjének választásánál elgondolkozni, eszes sorrendet (heurisztikát) keresni. Néhány ötlet: A sorrendet rekurzíven alakítjuk ki.

• A sorrendet hátulról elõre alakítjuk ki. A sorrendbe be nem sorolt csúcsok által feszített gráfot vizsgáljuk. Ezen gráf minimális fokú csúcsát ``nem veszélyesnek'' nyilvánítjuk és a be nem sorolt csúcsok közül a sorrendben utolsónak vesszük, az eddig besorolt csúcsok elé.
• A sorrendet elõrõl hátulra alakítjuk ki. A sorrendbe be nem sorolt csúcsok által feszített gráfot vizsgáljuk. Ezen gráf maximális fokú csúcsát ``veszélyesnek'' nyilvánítjuk és a be nem sorolt csúcsok közül a sorrendben elsõnek vesszük, az eddig besorolt csúcsok mögé.

Példa: Legyen G egy összefüggõ nem reguláris gráf. Ekkor csúcsainak alkalmas p sorrendjére x_p<₌ D(G).

Bizonyítás: Tetszõleges összefüggõ gráf csúcsait sorba tudjuk rendezni úgy, hogy az utolsó kivételével mindegyiknek legyen késõbbi szomszédja. Sõt sorrendünk utolsó pontja bármelyik csúcs lehet. Miért? Nem reguláris gráfunk esetén vegyük egy ilyen sorrendet, amelyben az utolsó csúcs fokszáma kisebb mint D(G). Legyen p ezen sorrend. A p-t követõ mohó algoritmus mindegyik csúcsnál D(G)-nél kevesebb tiltott színt ad, azaz egy D(G) színt tartalmazó paletta elegendõ.

Példa: Legyen G egy háromszorosan összefüggõ gráf, amely nem teljes. Ekkor csúcsainak alkalmas p sorrendjére x_p<₌ D(G).

Bizonyítás: G nem teljes, így található benne egy xz és egy yz él úgy, hogy x és y ne legyen összekötött. Miért? G háromszorosan összefüggõ, így G-x-y összefüggõ. A korábbi indoklás ötletét felhasználva G-x-y csúcsai sorbarendezhetõk úgy, hogy z legyen az utolsó elem, továbbá minden más csúcsnak legyen késõbbi szomszédja. Ezen sorrend elé x-et és y-t rakva G csúcsainak egy olyan sorrendjét kapjuk, amley az állítást igazolja: A z-tõl különbözõ csúcsok esetén amár színezett szomszédok elemszáma sem érheti el D(G)-t (lesz nem színezett szomszédjuk). z-nek lehet D(G) színezett szomszédja, de közte lesz x és y is, amelyek az 1 színt kapták.

Tétel: (Brooks) Legyen G egy összefüggõ gráf, amely nem teljes és nem páratlan kör. Ekkor csúcsainak alkalmas p sorrendjére x_p<₌ D(G).

Az elõzõ példából nem nehezen adódik. A technikai részletek nem szerepeltek az órán. Az érdeklõdõk megtalálhatják a bizonyítást a jegyzetben vagy interneten.

Példa: Legyen E a sík egy véges egyeneshalmaza, amleyrõl feltesszük, hogy semelyik három egyenesmek sincs közös pontja. Legyen M az E-beli egyenesek által kialakított metszéspontok halmaza. Két M-beli elem szomszédos, ha egy egyenesünkre esnek, de köztük nincs más metszépont. Ekkor M elemei 3 színnel kiszínezhetõk úgy, hogy a szomszédosak különbözõ színt kapjanak.

Bizonyítás: Ábránkat úgy helyezzük el, hogy a színezendõ metszépontok x koordinátái legyenek különbözõk. Az x koordináták szerinti növekvõ sorrendbe rendezzük a csúcsokat. Minden P metszéspont két egyenes metszete, amelyek tartalmazzák P szomszédait. A két egyenes közül mindegyik legfeljebb két szomszédot tartalmaz, amelyek közül csak az egyik lehet elõbb és csak az egyeik lehet késõbb a fent leírt sorrendben. Azaz a sorrendünk olyan, hogy eszerint végighaladva pontjainkon mindegyik aktuális pontnak maximum két megelõzó szomszédja lehet. Így ezen sorrend szerinti mohó színezés igazolja az állítást.

Definíció: Legyen I egy egyenes intervallumaiból alkotott véges rendszer. I metszet-gráfja az az egyszerû gráf, amely csúcsai I elemei és két csúcs akkor és csak akkor összekötött, ha az intervallumok metszik egymást.

Definíció: A G egyszerû gráf intervallumgráf, ha izomorf egy alkalmas intervallumrendszer metszetgráfjával. Egy intervallumgráfra úgy gondolhatunk, hogy csúcsi intervallumokkal címkézettek és élei azt jelölik, hogy két

Példa: Egy G intervallum gráf csúcsainak alkalmas p sorrendjére x_p(G)=x(G).

Bizonyítás: A csúcsokhoz rendeljünk intervallumokat, amelyek G intervallumgráfságát igazolják. Legyen p a csúcsokhoz rendelt intervallumok bal oldali végpontja szerinti sorrend. Ha a p szerinti mohó színezés egy csúcshoz (amely intervalluma legyen [a,z]) a k színt rendeli, akkor a csúcs már színezett szomszédai között elõ kell fordulnia az 1,2,...,k-1 színeknek. Egy csúcs már színezett szomszédaihoz olyan intervallumok talrtoznak, amelyek nem kezdõdhetnek késõbb mint [a,z] (már szinezettek) és metszik [a,z]-t (szomszédok). Így ezek az intervallumok tartalmazzák az a pontot. Ezen intervallumok közül\ egy 1 színû, egy 2 színû, ..., egy k-1 színû és maga [a,z] a csúcsokhoz rendelt intervallumok közül k darab úgy, hogy mindegyik tartalmaz egy koz's igazolja az állítást.

Definíció: Legyen I egy egyenes intervallumaiból alkotott véges rendszer. I metszet-gráfja az az egyszerû gráf, amely csúcsai I elemei és két csúcs akkor és csak akkor összekötött, ha az intervallumok metszik egymást.

Definíció: A G egyszerû gráf intervallumgráf, ha izomorf egy alkalmas intervallumrendszer metszetgráfjával. Egy intervallumgráfra úgy gondolhatunk, hogy csúcsi intervallumokkal címkézettek és élei azt jelölik, hogy két

Példa: Egy G intervallum gráf csúcsainak alkalmas p sorrendjére x_p(G)=x(G).

Bizonyítás: A csúcsokhoz rendeljünk intervallumokat, amelyek G intervallumgráfságát igazolják. Legyen p a csúcsokhoz rendelt intervallumok bal oldali végpontja szerinti sorrend. Ha a p szerinti mohó színezés egy csúcshoz (amely intervalluma legyen [a,z]) a k színt rendeli, akkor a csúcs már színezett szomszédai között elõ kell fordulnia az 1,2,...,k-1 színeknek. Egy csúcs már színezett szomszédaihoz olyan intervallumok talrtoznak, amelyek nem kezdõdhetnek késõbb mint [a,z] (már szinezettek) és metszik [a,z]-t (szomszédok). Így ezek az intervallumok tartalmazzák az a pontot. Ezen intervallumok közül\ egy 1 színû, egy 2 színû, ..., egy k-1 színû és maga [a,z] a csúcsokhoz rendelt intervallumok közül k darab úgy, hogy mindegyik tartalmaz egy közös pontot (a), azaz az intervallumok páronként metszõek. Az ezekhez tartozó k csúcs páronként összekötött, azaz minden jó színezésnek különbözõ színt kell adnia nekik. Speciálisan az optimális színezés is legalább k színt használ. Ez a megállapítás bizonyítja az állítást.

Definíció: Egy G hurokél-nélküli gráf lerajzolása alatt egy leképezést értünk, amely V(G) elemeihez különbözõ síkbeli pontokat, E(G) elemeihez önmagát nem metszõ folytonos görbéket rendel, amelyek kielégítik a következõket:

• egy xy élnek megfelelõ görbe két végpontja az x, illetve y csúcspontnak megfelelõ pontok, továbbá V(G) más elemének megfelelõ ponton nem halad át,
• két különbözõ élnek megfelelõ görbének csak véges sok közös pontja van, amikor is a két görbe átmetszi egymást.

A fenti definíció könnyen kiterjeszthetõ hurokéleket tartalmazó gráfokra is úgy, hogy a hurokéleknek megfelelõ görbe egy zárt, önmagát nem metszõ görbe legyen.

Akik számára a folytonos görbe ismeretlen, vagy túl absztrakt fogalom, azok a fogalom lényegének csonkítása nélkül gondolhatnak az éleket reprezentáló geometriai alakzatokra mint önmagukat nem metszõ törött vonalakra (szakaszok végpontjaikban csatlakozó véges sorozata).

Definíció: Egy lerajzolás szép lerajzolás, ha a lerajzolás feltételei mellett még az is teljesül, hogy

• két különbözõ élt reprezentáló görbének ne legyen közös belsõ pontja.

Definíció: Egy G gráf síkgráf, ha létezik szép síkra rajzolása.

Példa: Egyszerû síkgráfok csúcsainak van olyan p sorbaállítása, hogy x_p<₌6 teljesüljön.

Bizonyítás: Az alábbi lemma alapján minden egyszerû síkgráfban van legfeljebb ötödfokú csúcs. Emlékezzünk a következõ színezési sorrendet kialakító heurisztikára: A sorrendet hátulról elõre alakítjuk ki. A sorrendbe be nem sorolt csúcsok által feszített gráfot vizsgáljuk. Ezen gráf minimális fokú csúcsát ``nem veszélyesnek'' nyilvánítjuk és a be nem sorolt csúcsok közül a sorrendben utolsónak vesszük, az eddig besorolt csúcsok elé.

Ez egy olyan sorrendhez vezet, amely szerint színezve minden aktuális csúcsnak legfeljebb öt már színezett szomszédja lesz. Azaz egy hat színt tartalmazó paletta elég.

Lemma: Egy egyszerû síkgráfban van legfeljebb ötödfokú csúcs.

Lemma bizonyítása: Ha egy egyszerû síkgráfnak legalább 3 csúcsa van, akkor élszáma legfeljebb 3|V|-6. Így fokszámainak összege nem éri el 6|V|-t, azaz átlagos fokszáma 6-nál kisebb. Így létezik legfeljebb 5 fokú csúcsa. Ez tetszõleges síkgráfra igaz, hiszen ha csúcsok száma nem éri el a hármat, akkor a legfeljebb ötödfokú csúcs létezése nyilvánvaló.