Hurok színezés

A ciklusszínezés a szokásos gráfszínezés finomításának tekinthető . Egy címkézett gráf ciklikus kromatikus száma a következő ekvivalens módon (véges gráfokhoz) definiálható. $G$ $\chi _{c}(G)$

$\chi _{c}(G)$ egyenlő az infimummal az összes valós szám felett úgy, hogy van egy leképezés egy 1-es hosszúságú körre, és két szomszédos csúcs a kör mentén egymástól távol eső pontokra van leképezve. $r$ $V(G)$ $\geqslant {\tfrac {1}{r))$
$\chi _{c}(G)$ egyenlő a racionális számok feletti infimummal úgy, hogy van egy ciklusos csoportra való leképezés azzal a tulajdonsággal, hogy a szomszédos csúcsok egymástól távol lévő elemekre vannak leképezve . ${\tfrac {n}{k))$ $V(G)$ ${\mathbb {Z} }/n{\mathbb {Z} }$ $\geqslant k$
Egy irányított gráfban a ciklus kiegyensúlyozatlanságát úgy definiáljuk, hogy az értéket osztjuk az óramutató járásával megegyező irányú élek és az óramutató járásával ellentétes élek számából a kisebbel. Egy irányított gráf kiegyensúlyozatlanságát úgy definiáljuk , mint az összes ciklusra kiterjedő maximális kiegyensúlyozatlanságot. Most egyenlő a minimális kiegyensúlyozatlansággal a grafikon összes tájolásában . $C$ $|E(C)|$ $\chi _{c}(G)$ $G$

Ez viszonylag könnyen belátható (az 1. vagy 2. definíció használatával), de valójában . Ebben az értelemben azt mondjuk, hogy a ciklikus kromatikus szám finomítja a közönséges kromatikus számot. $\chi _{c}(G)\leqslant \chi (G)$ $\lceil \chi _{c}(G)\rceil =\chi (G)$

A ciklusszínezést eredetileg Vince [1] határozta meg , aki "csillagszínezésnek" nevezte.

A ciklusos színezés kettős a sehol zéró áramlás témájával , sőt, a ciklusos színezésnek természetes kettős fogalma van: "keringő áramlás".

Ciklikus teljes grafikonok

Körkörös teljes grafikon
Csúcsok	n
borda	${\tfrac {n(n-2k+1)}{2)),$
Heveder	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{egyébként))\end {tömb}}\jobbra.$
Kromatikus szám	⌈n/k⌉
Tulajdonságok	( n − 2k + 1) - Szabályos csúcs-tranzitív körkörös Hamilton -féle

Olyan egész számok esetén , amelyekben , a ciklikus teljes gráf (más néven ciklikus klikk ) olyan gráf, amelyben sok csúcs és él van az egymástól távol lévő elemek között . Vagyis a csúcsok számok , és az i csúcs szomszédos: $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

Például csak egy teljes gráf K n , míg a gráf izomorf a ciklusgráfhoz . $K_{\tfrac {n}{1))$ $K_{\tfrac {2n+1}{n))$ $C_{2n+1}$

Ilyen esetben a ciklusszínezés a fenti második definíció szerint egy ciklus teljes gráfba való homomorfizmusa . A kritikus körülmény ezeknél a gráfoknál az, hogy akkor és csak akkor ismeri el a homomorfizmust . Ez magyarázza a jelölést, hiszen ha a és racionális számok egyenlőek, akkor homomorfikusan egyenértékűek. Ezenkívül a homomorfizmus-rend a teljes gráfok által adott sorrendet sűrű renddé finomítja, és megfelel a racionális számoknak . Például $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

Illetve ezzel egyenértékűen

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

Az ábrán látható példa egy homomorfizmusként értelmezhető a Flower snartól a -ig , amely előtt áll , ami megfelel annak, hogy . $J_{5}$ $K_{\tfrac {5}{2}}\approx C_{5}$ $K_{3}$ $\chi _{c}(J_{5})\leqslant 2.5<3$

Lásd még

Ciklikus rang

Jegyzetek

↑ Vince, 1988 .

Irodalom

Adam Nadolski. Grafikonok körkörös színezése // Graph colorings. - Providence, R.I.: Amer. Math. Soc., 2004. - T. 352. - S. 123-137. - (Contemp. Math.). - doi : 10.1090/conm/352/09 .
Vince A. Csillagkromatikus szám // Journal of Graph Theory. - 1988. - T. 12 , sz. 4 . – S. 551–559 . - doi : 10.1002/jgt.3190120411 .
Zhu X. Circular kromatikus szám, felmérés // Discrete Mathematics. - 2001. - T. 229 , szám. 1-3 . – S. 371–410 . - doi : 10.1016/S0012-365X(00)00217-X .