Barvení smyčky

Cyklické zbarvení lze chápat jako zdokonalení běžného vybarvování grafů . Cyklické chromatické číslo označeného grafu lze definovat následujícími ekvivalentními (pro konečné grafy) způsoby. $G$ $\chi _{c}(G)$

$\chi _{c}(G)$ se rovná infimu přes všechna reálná čísla tak, že existuje zobrazení od do kruhu o délce rovné 1, se dvěma sousedními vrcholy mapovanými na body ve vzdálenosti podél kruhu. $r$ $V(G)$ $\geqslant {\tfrac {1}{r))$
$\chi _{c}(G)$ se rovná infimu nad racionálními čísly tak, že existuje zobrazení od do cyklické skupiny s vlastností, že sousední vrcholy jsou zobrazeny na prvky ve vzájemné vzdálenosti. ${\tfrac {n}{k))$ $V(G)$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$
V orientovaném grafu definujeme nevyváženost cyklu jako hodnotu dělenou menším počtem hran ve směru hodinových ručiček a počtem hran proti směru hodinových ručiček. Nevyváženost orientovaného grafu definujeme jako maximální nerovnováhu ve všech cyklech. Nyní se rovná minimální nevyváženosti přes všechny orientace grafu . $C$ $|E(C)|$ $\chi _{c}(G)$ $G$

Je poměrně snadné vidět, že (s použitím definice 1 nebo 2), ale ve skutečnosti . V tomto smyslu říkáme, že cyklické chromatické číslo zjemňuje běžné chromatické číslo. $\chi _{c}(G)\leqslant \chi (G)$ $\lceil \chi _{c}(G)\rceil =\chi (G)$

Cyklické zbarvení bylo původně definováno Vincem [1] , který to nazval „star coloring“.

Cyklické barvení je duální vzhledem k tématu nikde nulový tok a navíc cyklické barvení má přirozený duální koncept "cirkulujícího toku".

Cyklické kompletní grafy

Kruhový kompletní graf
Vrcholy	n
žebra	${\tfrac {n(n-2k+1)}{2)),$
obvod	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{jinak))\end {pole}}\vpravo.$
Chromatické číslo	⌈n/k⌉
Vlastnosti	( n − 2k + 1) - Regulární vertex-tranzitivní kruhový Hamiltonián

Pro celá čísla taková, že , cyklický úplný graf (také známý jako cyklická klika ) je graf s mnoha vrcholy a hranami mezi prvky ve vzájemné vzdálenosti. To znamená, že vrcholy jsou čísla a vrchol i sousedí s: $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,\tečky ,i+nk\mod n

Například je to jen úplný graf Kn , zatímco graf je izomorfní s grafem cyklu . $K_{\tfrac {n}{1))$ $K_{\tfrac {2n+1}{n))$ $C_{2n+1}$

V takovém případě je zbarvení cyklu podle druhé definice výše homomorfismem do grafu úplného cyklu. Kritická okolnost o těchto grafech je, že připouští homomorfismus tehdy a pouze tehdy, když . To vysvětluje zápis, protože pokud jsou racionální čísla a rovna, pak jsou homomorfně ekvivalentní. Pořadí homomorfismu navíc zpřesňuje pořadí dané úplnými grafy do hustého řádu a odpovídá racionálním číslům . Například $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}}\to K_{\tfrac {4}{1}}\to \dots

Nebo ekvivalentně

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

Příklad na obrázku lze interpretovat jako homomorfismus od květinového snark k , který přichází dříve , což odpovídá skutečnosti, že . $J_{5}$ $K_{\tfrac {5}{2}}\cca C_{5}$ $K_{3}$ $\chi _{c}(J_{5})\leqslant 2.5<3$

Viz také

Cyklická hodnost

Poznámky

↑ Vince, 1988 .

Literatura

Adam Nadolski. Kruhové vybarvování grafů // Barvení grafů. — Providence, R.I.: Amer. Matematika. Soc., 2004. - T. 352. - S. 123-137. - (Contemp. Math.). - doi : 10.1090/conm/352/09 .
Vince A. Hvězdné chromatické číslo // Journal of Graph Theory. - 1988. - T. 12 , no. 4 . — S. 551–559 . - doi : 10.1002/jgt.3190120411 .
Zhu X. Kruhové chromatické číslo, přehled // Diskrétní matematika. - 2001. - T. 229 , vydání. 1-3 . — S. 371–410 . - doi : 10.1016/S0012-365X(00)00217-X .