Gráfok színezése

A kromatikus szám $n$. Mivel a teljes gráfban bármely két csúcs éllel van összekötve, semelyik két csúcs nem kaphatja ugyanazt a színt egy érvényes jó színezés során. Így pontosan $n$ különböző színre van szükség.

Nem igaz. Ha egy páros gráf nem tartalmaz egyetlen élt sem (például egy izolált csúcsokból álló üres gráf), akkor a színezéséhez elegendő 1 szín. Abban az esetben, ha a páros gráf tartalmaz legalább egy élt, a kromatikus száma pontosan 2.

Ha $n$ páros szám, akkor a körgráf páros gráf is egyben, így a kromatikus száma 2 (felváltva színezhetők a csúcsok). Ha $n$ páratlan szám, a kör bejárása után az utolsó csúcs mindkét szomszédja különböző színű lenne 2 szín használata esetén, így szükséges egy harmadik szín. Ekkor a kromatikus szám 3.

Az élkromatikus szám 3. Mivel minden csúcs fokszáma 3, így legalább 3 színre biztosan szükség van. A 6 él színezhető 3 színnel úgy, hogy minden színhez 2 független élet rendelünk, azaz a szemközti élek kapják ugyanazt a színt.

Az Euler-féle poliédertételt alkalmazzuk összefüggő síkgráfokra: $c - e + t = 2$. Ahol $c$ a csúcsok, $e$ az élek, $t$ a tartományok száma. Behelyettesítve a megadott értékeket: $10 - 15 + t = 2$, amiből $t - 5 = 2$, tehát $t = 7$. A gráf 7 tartományra osztja a síkot, beleértve a külső, végtelen tartományt is.

Nem létezik. A matematikában bizonyított négyszíntétel (Appel és Haken, 1976) kimondja, hogy minden síkgráf kiszínezhető legfeljebb 4 különböző szín felhasználásával úgy, hogy ne legyen két szomszédos csúcs azonos színű.

A kromatikus száma 2. Minden fa páros gráf, mivel nem tartalmaz kört, így páratlan hosszúságú kört sem. Mivel a fának legalább két csúcsa és így legalább egy éle van, a kromatikus szám pontosan 2.

Ha $n \ge 3$, egy $n$ csúcsú egyszerű síkgráf maximális élszáma az Euler-formulából levezethető $e \le 3c - 6$ egyenlőtlenséggel számolható. Behelyettesítve $c = 10$-et: $e \le 3 \cdot 10 - 6 = 24$. Tehát maximum 24 éle lehet.

A kromatikus száma 2. Mivel ez a gráf definíció szerint páros gráf, a csúcsai két diszjunkt halmazra oszthatók úgy, hogy azonos halmazon belüli csúcsok nincsenek összekötve élekkel. Így az egyik halmaz minden csúcsa kaphatja az egyik színt, a másik halmaz pedig a másikat.

Nem lehetséges. Létezik egy tétel, mely szerint minden egyszerű síkgráfban lennie kell legalább egy olyan csúcsnak, amelynek a fokszáma legfeljebb 5. Ha minden csúcs fokszáma legalább 6 lenne, akkor az élszám az $e \ge \frac{6c}{2} = 3c$ feltételt elégítené ki, ami ellentmond az $e \le 3c - 6$ síkgráfokra vonatkozó élszámkorlátnak.

Kiválasztunk egy tetszőleges gyökércsúcsot, ezt $k$-féleképpen színezhetjük. A fa szerkezetéből adódóan minden további csúcsot úgy színezünk, hogy haladunk a gyökértől kifelé. Minden csúcsot a szülőjétől eltérő színre kell festeni, amire mindegyiknél pontosan $k-1$ lehetőség van. Mivel $n-1$ ilyen csúcs van, az összes lehetőség száma $k \cdot (k-1)^{n-1}$.

Kuratowski tétele szerint egy gráf akkor és csak akkor síkgráf, ha nem tartalmaz a $K_5$ teljes gráffal, vagy a $K_{3,3}$ teljes páros gráffal topologikusan izomorf részgráfot (azaz nem tartalmaz olyan részgráfot, amely élek felosztásával ezekből származtatható).

Az élkromatikus szám 5. A gráf maximális fokszáma 4, így legalább 4 szín kéne. Azonban az 5 csúcs miatt bármely adott színű élek halmaza független éleket alkot, amelyek egyszerre legfeljebb 2 élt fedhetnek le (mivel minden él 2 csúcsot foglal le, és $2 \cdot 2 \le 5$). Összesen 10 éle van, így ha egy szín max 2 élt fed le, akkor legalább $10/2 = 5$ színre van szükség.

Igen, létezik. Ilyen gráf például a Grötzsch-gráf, amely 11 csúcsú és 20 élű. Továbbá a Mycielski-konstrukcióval bizonyítható, hogy tetszőlegesen nagy kromatikus számú, ugyanakkor háromszögmentes gráf is konstruálható.

A térkép tartományai felelnek meg pontosan a duális gráf csúcsainak. Két tartomány közös határvonala pedig megfelel a duális gráf egy-egy élének, amely ezen két csúcsot összeköti. Így a térkép tartományainak érvényes színezése matematikai értelemben teljesen ekvivalens a duális gráf (amely szintén síkgráf) csúcsszínezésével.

Brooks tétele szerint az ilyen összefüggő gráfok kromatikus száma legfeljebb $\Delta$. Bár egy mohó algoritmussal garantálható lenne $\Delta + 1$ szín elégségessége bármely gráfra, Brooks kimutatta, hogy a kivételes esetektől (teljes gráfok és páratlan körök) eltekintve $\Delta$ szín mindig elegendő a helyes csúcsszínezéshez.

A peremen elhelyezkedő csúcsok egy páros hosszú kört alkotnak, amely felváltva 2 színnel érvényesen kiszínezhető. A középső, úgynevezett agy-csúcs azonban össze van kötve a perem minden egyes csúcsával, így nem kaphatja az előző 2 szín egyikét sem. Ezért pontosan egy 3. színre van szüksége, így a kromatikus szám 3.

Kőnig tétele alapján egy gráf akkor és csak akkor páros gráf, ha nem tartalmaz páratlan hosszúságú kört. Mivel a feltétel szerint nincsenek benne páratlan körök, a gráf páros. Egy legalább egy élet tartalmazó páros gráf kromatikus száma pedig mindig pontosan 2.

A Petersen-gráf nem síkgráf. Ennek bizonyítása Kuratowski tételén alapszik, ugyanis a Petersen-gráf megfelelő éleinek összevonásával vagy csúcsok elhagyásával belátható, hogy tartalmaz a $K_{3,3}$ teljes páros gráffal topologikusan izomorf részgráfot.

Nincs. Kőnig vonalszínezési tétele (élkromatikus tétele) kimondja, hogy minden páros gráf élkromatikus száma pontosan megegyezik a maximális fokszámával, azaz $\chi'(G) = \Delta(G)$. Tehát semmilyen páros gráfnál nem lehet nagyobb az élkromatikus szám a maximális fokszámnál.