Vizing-tétel

A Vizing-tétel alsó és felső korlátot ad egy egyszerű gráf élkromatikus számára. A tételt Vagyim Georgijevics Vizing 1964-ben bizonyította be. A tétel szerint egy egyszerű gráf élkromatikus száma legfeljebb eggyel nagyobb a maximális fokszámánál, azaz ha a gráf minden csúcsában k-nál kevesebb él találkozik, akkor ki tudjuk színezni az éleit legfeljebb k színnel. Képlettel:

$\mathrm{\Delta }(G)\le {\chi }_e(G)\le \mathrm{\Delta }(G)+1$

Az irányítatlan gráfok két osztályba particionálhatók: melyek színezéséhez $\mathrm{\Delta }$ szín elegendő, azok az „első csoportba” sorolt gráfok (class one), melyekhez $\mathrm{\Delta }+1$ szín szükséges, azok a „második csoportba” sorolt gráfok (class two).

Bizonyítás

A bizonyításban megmutatjuk, hogy minden esetben ki tudjuk színezni a gráf éleit $\mathrm{\Delta }(G)+1$ színnel. Kezdjük el színezni a gráfot, és tegyük fel, hogy egy $x$ és $y_1$ pontok közötti élet még nem színeztünk ki. A gráf minden $v$ csúcsához rendeljünk egy $c(v)$ színt úgy, hogy $c(v)$ azt a színt jelölje ami még nem szerepel az egyik $v$-ből kiinduló élen sem. Ilyen azért lesz mindig, mert egy csúcsból legfeljebb $\mathrm{\Delta }(G)$ él indulhat ki. Ha $c(x)$ = $c(y_1)$ akkor ezzel a $c(x)$ színnel kiszínezhetjük az $x$ és $y_1$ között futó élet. Tegyük fel, hogy $c(x)$ $\ne$ $c(y_1)$. Ekkor, ha $x$-ből nem indul ki $c(y_1)$ színű él, akkor az $x$ és $y_1$ között futó élet kiszínezhetjük ezzel a színnel. Egyébként, tegyük fel, hogy $x$ és $x$ egy $y_2$ szomszédja között futó él színe $c(y_1)$. Most, ha $x$-ből nem indul ki $c(y_2)$ színű él, akkor ezzel a színnel színezzük az $x,y_2$ élet, és ekkor már nem indul ki $x$-ből $c(y_1)$ színű él. Egyébként feltehetjük, hogy $x$ és egy $y_3$ csúcs közötti él színe $c(y_2)$, és folytatjuk az előző módon az algoritmust az $y_4$, $y_5$, stb. pontokkal. Csak egy esetben nem tudjuk folytatni az algoritmust: ha találunk egy olyan $n$-t, hogy az $x$ és $y_n$ közötti él színe $c(y_{n-1})$, de egy $j$ (1 $\le$ $j$ < $n$) indexre $c(y_n)$ = $c(y_j)$. Ebben az esetben tekintsük $G$-nek azt a részgráfját, melyben pontosan azok az élek szerepelnek, melyek $G$-ben $c(x)$ vagy $c(y_n)$ színűek. Ebben a gráfban $\mathrm{\Delta }$ = 2, $x$-ből nem indul ki $c(x)$ színű él, és $y_n$ és $y_j$-ből pedig nem indul ki $c(y_n)$ színű él. Ez azt jelenti, hogy ennek a három pontnak a fokszáma maximum 1, és $x$ $y_j$ vagy $y_n$-től különböző komponensben van (mivelhogy a gráf izolált pontokból, utakból és körökből állhat a maximális fokszám miatt). Cseréljük fel az élek színét abban a komponensben, melyben $x$ nem található, viszont $y_j$ vagy $y_n$ igen. Ha például $y_j$ volt más komponensben, akkor elértük hogy $c(y_j)$ = $c(x)$. Most már az $x$ és $y_j$ közötti élet színezhetjük $c(x)$-szel, az $x,y_{j-1}$ él színét $c(y_{j-1})$-gyel, és így tovább amíg a végén $x,y_1$-et $c(y_1)$-gyel színezzük. Ezzel egy jó színezést kaptunk, és bebizonyítottuk az állítást.

Hivatkozások

• Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 85,86.