Chromatické číslo

Chromatické číslo grafu G je minimální počet barev, ve kterém je možné obarvit [1] vrcholy grafu G tak, aby konce libovolné hrany měly různé barvy. Obvykle se označuje χ( G ).

Definice

Barevné číslo grafu je minimální počet , takže množinu vrcholů grafu lze rozdělit do disjunktních tříd : $k$ $PROTI$ $k$ $C_{1},C_{2},\ldots ,C_{k}$

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

takové, že vrcholy v každé třídě jsou nezávislé , to znamená, že žádná hrana grafu nespojuje vrcholy stejné třídy.

Související definice

K-barvitelný graf je graf, jehož chromatické číslo nepřesahuje . To znamená, že jeho vrcholy mohou být obarveny maximálně barvami takovým způsobem, že každá hrana končí jinou barvou. $K$ $K$
K-chromatický graf je graf, jehož chromatické číslo je . Tzn., že vrcholy grafu lze obarvit barvami tak, že jakákoli hrana končí různými barvami, ale takto již nelze vybarvovat barvami. $K$ $K$ $K-1$

Barvení okrajů

Chromatická třída grafu G je minimální počet barev, ve kterých lze obarvit okraje grafu G tak, aby sousední hrany měly různé barvy. Označeno χ'( G ). Problém obarvení hran libovolného rovinného kubického grafu bez mostů třemi barvami je ekvivalentní slavnému problému čtyř barev . Barvení hran definuje 1-faktorizaci grafu.

Chromatický polynom

Pokud uvážíme počet různých zabarvení označeného grafu jako funkci dostupného počtu barev t , pak se ukáže, že tato funkce bude vždy polynom v t . Tento fakt objevili Birkhoff a Lewis [2] při pokusu dokázat problém čtyř barev .

Chromatické polynomy některých grafů

Trojúhelník $K_{3}$	$t(t-1)(t-2)$
Kompletní graf $K_n$	$t(t-1)(t-2)...(t-(n-1))$
strom s vrcholy $n$	$t(t-1)^{{n-1}}$
Cyklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
hrabě z Petersenu	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Nalezení chromatického polynomu libovolného grafu

Pro vrcholový graf je chromatický polynom $t$

|V(G)|=1\šipka doprava P(G,t)=t.

chromatický polynom grafu je roven součinu chromatických polynomů jeho složek

G_{1}\cap G_{2}=\prázdná sada \Šipka doprava P((G_{1}\pohár G_{2}),t)=P(G_{1},t)P(G_{2},t ).

Existuje také rekurzivní vztah - Zykovova věta [3] , tzv. odstraňovací a kontrakční vzorec

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

kde a jsou sousední vrcholy, je graf získaný z grafu odstraněním hrany a je graf získaný z grafu stažením hrany do bodu. Můžete použít ekvivalentní vzorec $u$ $proti$ $Fotr)$ $G$ $(u, v),$ $Fotr)$ $G$ $(u,v)$

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

kde a jsou nesousedící vrcholy a je graf získaný z grafu přidáním hrany $u$ $proti$ $G+(u,v)$ $G$ $(u,v).$

Vlastnosti chromatického polynomu

Pro všechna kladná celá čísla $t$

P(G,t)\geq 0.

Chromatické číslo je nejmenší kladné celé číslo , pro které $\chi (G)$ $t$

P(G,t)>0.

Stupeň chromatického polynomu se rovná počtu vrcholů:

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

Zobecnění

Také chromatické číslo lze vzít v úvahu pro jiné objekty, jako jsou metrické prostory . Chromatické číslo roviny je tedy minimální počet barev χ, pro které existuje takové zabarvení všech bodů roviny jednou z barev, že žádné dva body stejné barvy nejsou ve vzdálenosti přesně 1 od každého. jiný. Totéž platí pro jakoukoli vesmírnou dimenzi. Je elementárně dokázáno, že pro letadlo se ale dlouho nedalo posunout dál. 8. dubna 2018 britský matematik Aubrey de Gray dokázal, že [4] [5] . Tento problém se nazývá Nelson-Erdős-Hadwigerův problém . $4\leqslant\chi\leqslant 7$ $\chi >4$

Význam pro teorii grafů

Mnoho hlubokých problémů v teorii grafů lze snadno formulovat z hlediska vybarvování. Nejznámější z těchto problémů, problém čtyř barev , byl nyní vyřešen, ale objevují se nové, jako je zobecnění problému čtyř barev, Hadwigerův dohad .

Viz také

Poznámky

↑ Omalovánka
↑ Birkhoff, GD a Lewis, DC "Chromatické polynomy." Trans. amer. Matematika. soc. 60, 355-451, 1946.
↑ Tato doména je zaparkována společností Timeweb
↑ de Grey, Aubrey DNJ (2018-04-08), chromatické číslo letadla je alespoň 5
↑ Vladimír Koroljov. Matematici postrádali čtyři barvy k obarvení letadla . nplus1.ru. Datum přístupu: 11. dubna 2018. (neurčitý)

Literatura

O. Ore . Teorie grafů. — M .: Nauka, 1986.