Kromatisk tal

Det kromatiske antal af grafen G er det mindste antal farver, hvor det er muligt at farve [1] hjørnerne af grafen G, så enderne af enhver kant har forskellige farver. Normalt betegnet χ( G ).

Definition

Det kromatiske antal af en graf er det mindste antal , således at sættet af grafens hjørnepunkter kan opdeles i usammenhængende klasser : $k$ $V$ $k$ $C_{1},C_{2},\ldots ,C_{k}$

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

sådan at hjørnerne i hver klasse er uafhængige , det vil sige, at ingen grafkant forbinder hjørner af samme klasse.

Relaterede definitioner

En K-farverbar graf er en graf, hvis kromatiske tal ikke overstiger . Det vil sige, at dens hjørner ikke kan farves med mere end farver på en sådan måde, at hver kant ender i en anden farve. $K$ $K$
En K-kromatisk graf er en graf, hvis kromatiske tal er . Det vil sige, at grafens hjørner kan farves med farver, så enhver kant ender i forskellige farver, men det er ikke længere muligt at farvelægge med farver på denne måde. $K$ $K$ $K-1$

Kantfarvning

Den kromatiske klasse af en graf G er det mindste antal farver, hvor kanterne af grafen G kan farves, så tilstødende kanter har forskellige farver. Betegnes χ'( G ). Problemet med kantfarvning af en vilkårlig plan kubisk graf uden broer med tre farver svarer til det berømte firefarveproblem . Kantfarvningen definerer en 1-faktorisering af en graf.

Kromatisk polynomium

Hvis vi betragter antallet af forskellige farvninger af en mærket graf som en funktion af det tilgængelige antal farver t , så viser det sig, at denne funktion altid vil være et polynomium i t . Dette faktum blev opdaget af Birkhoff og Lewis [2] mens de forsøgte at bevise firefarveproblemet .

Kromatiske polynomier af nogle grafer

Trekant $K_{3}$	$t(t-1)(t-2)$
Komplet graf $K_n$	$t(t-1)(t-2)...(t-(n-1))$
træ med toppunkter $n$	$t(t-1)^{{n-1}}$
Cyklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Greve af Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Find det kromatiske polynomium for en vilkårlig graf

For en toppunktsgraf er det kromatiske polynomium $t$

|V(G)|=1\Højrepil P(G,t)=t.

Det kromatiske polynomium i en graf er lig med produktet af de kromatiske polynomier af dens komponenter

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

Der er også en rekursiv relation - Zykovs sætning [3] , den såkaldte fjernelses- og kontraktionsformel

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

hvor og er tilstødende hjørner, er en graf opnået fra en graf ved at fjerne en kant , og er en graf opnået fra en graf ved at trække en kant sammen til et punkt. Du kan bruge den tilsvarende formel $u$ $v$ $G-(u,v)$ $G$ $(u, v),$ $G/(u,v)$ $G$ $(u,v)$

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

hvor og er ikke-tilstødende hjørner, og er grafen opnået fra grafen ved at tilføje en kant $u$ $v$ $G+(u,v)$ $G$ $(u,v).$

Egenskaber for det kromatiske polynomium

For alle positive heltal $t$

P(G,t)\geq 0.

Det kromatiske tal er det mindste positive heltal , for hvilket $\chi (G)$ $t$

P(G,t)>0.

Graden af et kromatisk polynomium er lig med antallet af hjørner:

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

Generaliseringer

Det kromatiske tal kan også tages i betragtning for andre objekter, såsom metriske mellemrum . Således er det kromatiske antal af en plan det mindste antal farver χ, for hvilke der er en sådan farvning af alle punkter på planet i en af farverne, at ikke to punkter af samme farve er i en afstand på nøjagtig 1 fra hver Andet. Det samme gælder for enhver rumdimension. Det er elementært bevist, at for flyet var det dog ikke muligt at bevæge sig længere i lang tid. Den 8. april 2018 beviste den britiske matematiker Aubrey de Gray , at [4] [5] . Dette problem kaldes Nelson-Erdős-Hadwiger-problemet . $4\leqslant\chi\leqslant 7$ $\chi >4$

Betydning for grafteori

Mange dybe problemer i grafteori er let formuleret med hensyn til farvelægning. Det mest berømte af disse problemer, firefarveproblemet , er nu blevet løst, men nye dukker op, såsom en generalisering af firefarveproblemet, Hadwiger-formodningen .

Se også

Noter

↑ Farvelægningsside
↑ Birkhoff, GD og Lewis, DC "Chromatic Polynomials." Trans. amer. Matematik. soc. 60, 355-451, 1946.
↑ Dette domæne er parkeret af Timeweb
↑ de Grey, Aubrey DNJ (2018-04-08), Flyets kromatiske tal er mindst 5
↑ Vladimir Korolev. Matematikere manglede fire farver til at farve flyet . nplus1.ru. Dato for adgang: 11. april 2018. (ubestemt)

Litteratur

O. Ore . Grafteori. — M .: Nauka, 1986.