Kromatikus szám

A G gráf kromatikus száma az a minimális színszám, amelyben lehetséges színezni [1] a G gráf csúcsait úgy, hogy bármely él végei különböző színűek legyenek. Általában χ( G ).

Definíció

A gráf kromatikus száma az a minimális szám , amelynél a gráf csúcsok halmaza diszjunkt osztályokra osztható : $k$ $V$ $k$ $C_{1},C_{2},\ldots ,C_{k}$

V=\bigcup _{i}^{{}}C_{i};\ C_{i}\cap C_{j}=\varnothing ,

úgy, hogy az egyes osztályok csúcsai függetlenek legyenek , vagyis egyetlen gráfél sem köti össze ugyanazon osztály csúcsait.

Kapcsolódó definíciók

A K-színezhető gráf olyan gráf, amelynek kromatikus száma nem haladja meg a -t . Vagyis a csúcsait legfeljebb színnel lehet színezni úgy, hogy minden él más-más színben végződjön. $K$ $K$
A K-kromatikus gráf olyan gráf, amelynek kromatikus száma . Vagyis a gráf csúcsai színekkel színezhetők úgy, hogy bármelyik él más-más színben végződjön, de színekkel így már nem lehet színezni . $K$ $K$ $K-1$

Élszínezés

A G gráf kromatikus osztálya az a minimális színszám, amelyben a G gráf élei kiszínezhetők úgy, hogy a szomszédos élek különböző színűek legyenek. Jelölve χ'( G ). Egy tetszőleges síkbeli köbös gráf élszínezésének problémája hidak nélkül három színnel megegyezik a híres Négyszín Problémával . Az élszínezés a gráf 1-tényezősségét határozza meg.

Kromatikus polinom

Ha egy felcímkézett gráf különböző színezéseinek számát tekintjük a rendelkezésre álló t színek számának függvényében , akkor kiderül, hogy ez a függvény mindig polinom lesz t -ben . Ezt a tényt Birkhoff és Lewis [2] fedezte fel, miközben megpróbálta bizonyítani a négy szín problémáját .

Egyes gráfok kromatikus polinomjai

Háromszög $K_{3}$	$t(t-1)(t-2)$
Teljes grafikon $K_n$	$t(t-1)(t-2)...(t-(n-1))$
fa csúcsokkal _ $n$	$t(t-1)^{{n-1}}$
Ciklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen grófja	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Tetszőleges gráf kromatikus polinomjának megkeresése

Csúcsgráf esetén a kromatikus polinom az $t$

|V(G)|=1\Jobbra P(G,t)=t.

Egy gráf kromatikus polinomja egyenlő az összetevőinek kromatikus polinomjainak szorzatával

G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t ).

Létezik egy rekurzív reláció is - Zykov-tétel [3] , az úgynevezett eltávolítási és összehúzási képlet

P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),

ahol és a szomszédos csúcsok, egy gráfból egy él eltávolításával nyert gráf, és egy gráfból, amelyet egy élnek egy pontba húzásával kapunk. Használhatja az egyenértékű képletet $u$ $v$ $Tulaj)$ $G$ $(u, v),$ $Tulaj)$ $G$ $(u,v)$

P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),

ahol és a nem szomszédos csúcsok, és a gráfból egy él hozzáadásával kapott gráf $u$ $v$ $G+(u,v)$ $G$ $(u,v).$

A kromatikus polinom tulajdonságai

Minden pozitív egész számra $t$

P(G,t)\geq 0.

A kromatikus szám az a legkisebb pozitív egész szám , amelyre $\chi (G)$ $t$

P(G,t)>0.

A kromatikus polinom foka megegyezik a csúcsok számával:

\deg P(G,t)=|V(G)|

Általánosítások

Ezenkívül a kromatikus szám figyelembe vehető más objektumok, például metrikus terek esetében is . Így egy sík kromatikus száma az a minimális színszám χ, amelynél a sík összes pontja olyan színezésű az egyik színben, hogy nincs két azonos színű pont egymástól pontosan 1 távolságra. Egyéb. Ugyanez igaz bármely térdimenzióra. Alapvetően bebizonyosodott, hogy a gép számára azonban sokáig nem lehetett továbbmenni. 2018. április 8-án Aubrey de Gray brit matematikus bebizonyította, hogy [4] [5] . Ezt a problémát Nelson-Erdős-Hadwiger problémának nevezik . $4\leqslant\chi\leqslant 7$ $\chi >4$

Jelentősége a gráfelmélet szempontjából

A gráfelméletben sok mély probléma könnyen megfogalmazható a színezés szempontjából. E problémák közül a leghíresebb, a négyszín-probléma már megoldódott, de újak is megjelennek, mint például a négy szín probléma általánosítása, a Hadwiger-sejtés .

Lásd még

Jegyzetek

↑ Színező oldal
↑ Birkhoff, GD és Lewis, DC "Kromatikus polinomok". Trans. amer. Math. szoc. 60, 355-451, 1946.
↑ Ezt a domaint a Timeweb parkolta
↑ de Grey, Aubrey DNJ (2018-04-08), A sík kromatikus száma legalább 5
↑ Vlagyimir Koroljev. A matematikusoknak négy szín hiányzott a sík színezéséhez . nplus1.ru. Hozzáférés időpontja: 2018. április 11. (határozatlan)

Irodalom

O. Ore . Gráfelmélet. - M .: Nauka, 1986.