Silmukan väritys

Syklivärjäystä voidaan pitää tavallisen graafin värityksen jalostuksena . Leimatun graafin syklinen kromaattinen luku voidaan määritellä seuraavilla vastaavilla tavoilla (ääreisille graafille). $G$ $\chi _{c}(G)$

$\chi _{c}(G)$ on yhtä suuri kuin kaikkien reaalilukujen infimum siten, että on kuvaus ympyrästä, jonka pituus on 1, ja kaksi vierekkäistä kärkeä on kartoitettu pisteisiin, jotka ovat etäisyyden päässä ympyrää pitkin. $r$ $V(G)$ $\geqslant {\tfrac {1}{r))$
$\chi _{c}(G)$ on yhtä suuri kuin infimum rationaalilukujen yläpuolella siten, että on kohdistus sykliseen ryhmään , jolla on ominaisuus, että vierekkäiset kärjet kuvataan elementeille, jotka ovat etäisyyden päässä toisistaan. ${\tfrac {n}{k))$ $V(G)$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$
Suunnatussa graafissa määritämme syklin epätasapainon arvona jaettuna myötäpäivään olevien reunojen lukumäärällä ja vastapäivään olevien reunojen lukumäärällä pienemmällä. Suunnatun graafin epätasapaino määritellään kaikkien syklien suurimmaksi epätasapainoksi. Nyt on yhtä suuri kuin pienin epätasapaino kaavion kaikissa suuntauksissa . $C$ $|E(C)|$ $\chi _{c}(G)$ $G$

Se on suhteellisen helppo nähdä (käyttäen määritelmää 1 tai 2), mutta itse asiassa . Tässä mielessä sanomme, että syklinen kromaattinen luku jalostaa tavallista kromaattista lukua. $\chi _{c}(G)\leqslant \chi (G)$ $\lceil \chi _{c}(G)\rceil =\chi (G)$

Cycle värityksen määritteli alun perin Vince [1] , joka kutsui sitä "tähtivärjäykseksi".

Jaksoväritys liittyy kahteen aiheeseen nollan virtauksen kanssa, ja lisäksi syklivärjäyksellä on luonnollinen kaksoiskäsite "kiertovirtaus".

Sykliset täydelliset kaaviot

Pyöreä täydellinen kaavio
Huiput	n
kylkiluut	${\tfrac {n(n-2k+1)}{2)),$
Ympärysmitta	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\teksti{muuten))\end {array}}\right.$
Kromaattinen numero	⌈n/k⌉
Ominaisuudet	( n − 2k + 1) - Säännöllinen pistetransitiivinen pyöreä Hamiltonin

Sellaisten kokonaislukujen kohdalla syklinen täydellinen graafi (tunnetaan myös nimellä syklinen klikki ) on graafi, jossa on useita pisteitä ja reunoja eri etäisyyden päässä toisistaan olevien elementtien välillä. Eli kärjet ovat numeroita ja kärki i on vieressä: $n,k$ $n\geqslant 2k$ $K_{\tfrac {n}{k))$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$ ${\näyttötyyli {0,1,...,''n''-1}}$

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

Esimerkiksi on vain täydellinen graafi K n , kun taas graafi on isomorfinen syklikuvaajan kanssa . $K_{\tfrac {n}{1))$ $K_{\tfrac {2n+1}{n))$ $C_{2n+1}$

Tällaisessa tapauksessa syklin värjäys, yllä olevan toisen määritelmän mukaan, on homomorfismi syklin täydelliseksi graafiksi. Kriittinen seikka näissä kaavioissa on, että se myöntää homomorfismin jos ja vain jos . Tämä selittää merkinnän, koska jos rationaaliluvut ja ovat yhtä suuret, ne ovat homomorfisesti ekvivalentteja. Lisäksi homomorfismijärjestys jalostaa täydellisten graafien antamaa järjestystä tiheäksi järjestykseksi ja vastaa rationaalilukuja . Esimerkiksi $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

Tai vastaavasti

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

Kuvan esimerkki voidaan tulkita homomorfismina Flower snarista , joka tulee ennen , mikä vastaa sitä tosiasiaa, että . $J_{5}$ $K_{\tfrac {5}{2}}\noin C_{5}$ $K_{3}$ $\chi _{c}(J_{5})\leqslant 2.5<3$

Katso myös

Syklinen arvosana

Muistiinpanot

↑ Vince, 1988 .

Kirjallisuus

Adam Nadolski. Kaavioiden pyöreä väritys // Graafisten väritykset. - Providence, R.I.: Amer. Matematiikka. Soc., 2004. - T. 352. - S. 123-137. - (Ajatteleva matematiikka). - doi : 10.1090/conm/352/09 .
Vince A. Tähtien kromaattinen luku // Journal of Graph Theory. - 1988. - T. 12 , no. 4 . - S. 551-559 . - doi : 10.1002/jgt.3190120411 .
Zhu X. Circular kromaattinen luku, tutkimus // Discrete Mathematics. - 2001. - T. 229 , numero. 1-3 . — S. 371–410 . - doi : 10.1016/S0012-365X(00)00217-X .