Løkkefarvning

Cyklusfarvning kan ses som en forfining af almindelig graffarvning . Det cykliske kromatiske tal for en mærket graf kan defineres på følgende ækvivalente (for endelige grafer) måder. $G$ $\chi _{c}(G)$

$\chi _{c}(G)$ er lig med infimum over alle reelle tal, således at der er en afbildning fra til en cirkel med længde lig med 1, med to tilstødende hjørner afbildet til punkter i en afstand langs cirklen. $r$ $V(G)$ $\geqslant {\tfrac {1}{r))$
$\chi _{c}(G)$ er lig med infimum over rationelle tal, således at der er en afbildning fra til en cyklisk gruppe med den egenskab, at tilstødende hjørner er afbildet til elementer i en afstand fra hinanden. ${\tfrac {n}{k))$ $V(G)$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$
I en rettet graf definerer vi cyklusubalancen som værdien divideret med den mindste af antallet af kanter med uret og antallet af kanter mod uret. Vi definerer ubalancen i en rettet graf som den maksimale ubalance over alle cyklusser. Nu, er lig med minimum ubalance over alle orienteringer af grafen . $C$ $|E(C)|$ $\chi _{c}(G)$ $G$

Det er relativt let at se det (ved at bruge definition 1 eller 2), men faktisk . I denne forstand siger vi, at det cykliske kromatiske tal forfiner det almindelige kromatiske tal. $\chi _{c}(G)\leqslant \chi (G)$ $\lceil \chi _{c}(G)\rceil =\chi (G)$

Cyklusfarvning blev oprindeligt defineret af Vince [1] , som kaldte det "stjernefarvning".

Cyklusfarvning er dobbelt i forhold til emnet ingensteds nul flow , og desuden har cyklusfarvning et naturligt dobbeltbegreb om "cirkulerende flow".

Cykliske komplette grafer

Cirkulær komplet graf
Toppe	n
ribben	${\tfrac {n(n-2k+1)}{2)),$
Omkreds	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{ellers))\end {array}}\right.$
Kromatisk tal	⌈n/k⌉
Ejendomme	( n − 2k + 1) - Regulær vertex-transitiv cirkulær Hamiltonian

For heltal sådan , er en cyklisk komplet graf (også kendt som en cyklisk klike ) en graf med mange hjørner og kanter mellem elementer i en afstand fra hinanden. Det vil sige, at hjørnerne er tal, og toppunktet i støder op til: $n,k$ $n\geqslant 2k$ $K_{\tfrac {n}{k))$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$ ${0,1,...,''n''-1}$

i+k,i+k+1,\dots ,i+nk\mod n

For eksempel er kun en komplet graf K n , mens grafen er isomorf i forhold til cyklusgrafen . $K_{\tfrac {n}{1))$ $K_{\tfrac {2n+1}{n))$ $C_{2n+1}$

I et sådant tilfælde er en cyklusfarvning ifølge den anden definition ovenfor en homomorfi til en cyklus komplet graf. Den kritiske omstændighed ved disse grafer er, at den indrømmer en homomorfi til hvis og kun hvis . Dette forklarer notationen, da hvis de rationelle tal og er ens, så er de homomorfisk ækvivalente. Desuden forfiner homomorfi-rækkefølgen rækkefølgen givet af komplette grafer til en tæt rækkefølge og svarer til de rationelle tal . For eksempel $K_{\tfrac {a}{b))$ $K_{\tfrac {c}{d))$ ${\tfrac {a}{b}}\leqslant {\tfrac {c}{d}}$ ${\tfrac {a}{b))$ ${\tfrac {c}{d))$ $K_{\tfrac {a}{b))$ $K_{\tfrac {c}{d))$ $\geqslant 2$

K_{\tfrac {2}{1}}\to K_{\tfrac {5}{2}}\to K_{\tfrac {7}{3}}\to \dots \to K_{\tfrac {3}{1}}\til K_{\tfrac {4}{1}}\til \dots

Eller tilsvarende

K_{2}\to C_{5}\to C_{7}\to \dots \to K_{3}\to K_{4}\to \dots

Eksemplet på figuren kan tolkes som en homomorfi fra Blomstersnarken til , som kommer før , hvilket svarer til at . $J_{5}$ $K_{\tfrac {5}{2}}\approx C_{5}$ $K_{3}$ $\chi _{c}(J_{5})\leqslant 2.5<3$

Se også

Cyklisk rang

Noter

↑ Vince, 1988 .

Litteratur

Adam Nadolski. Cirkulær farvning af grafer // Graffarvninger. — Providence, R.I.: Amer. Matematik. Soc., 2004. - T. 352. - S. 123-137. - (Kontempl. Matematik.). - doi : 10.1090/conm/352/09 .
Vince A. Star kromatisk nummer // Journal of Graph Theory. - 1988. - T. 12 , no. 4 . — S. 551–559 . - doi : 10.1002/jgt.3190120411 .
Zhu X. Cirkulært kromatisk tal, en undersøgelse // Diskret matematik. - 2001. - T. 229 , udg. 1-3 . — S. 371–410 . - doi : 10.1016/S0012-365X(00)00217-X .