Kolorystyka na okrągło

Liczba chromatyczna snarka kwiatu J ₅ wynosi 3, ale okrągła liczba chromatyczna wynosi ≤ 5/2.

W teorii grafów kolorowanie kołowe jest rodzajem kolorowania, które można postrzegać jako udoskonalenie zwykłego kolorowania grafów . Okrągła liczba chromatyczna wykresu , oznaczona $,$$być$ podana za pomocą dowolnej z poniższych definicji, z których grafy skończone).

1. ${\ Displaystyle \ chi _ {c} (G)}$ jest infimum nad wszystkimi liczbami rzeczywistymi ${\ displaystyle r},$ tak że istnieje mapa z ${\ Displaystyle V (G)}$ do okręgu o obwodzie 1 z właściwością, że dowolne dwa sąsiednie wierzchołki są odwzorowywane na punkty w $okręgu$ .
2. ${\ Displaystyle \ chi _ {c} (G)}$ jest infimum nad wszystkimi liczbami wymiernymi ${\ Displaystyle {\ tfrac {n} {k}}},$ tak że istnieje mapa z ${\ Displaystyle V (G)}$ do grupy cyklicznej ${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$ z właściwością, że sąsiednie wierzchołki są odwzorowywane na elementy w odległości ${\ displaystyle \geq k}$ od siebie.
3. $|$ zorientowanym wykresie ${\ displaystyle | E (C) |}$ nierównowagę cyklu na podzielone przez minimalną liczbę krawędzi skierowanych zgodnie z ruchem wskazówek zegara i liczbę krawędzi skierowanych przeciwnie do ruchu wskazówek zegara. Zdefiniuj nierównowagę zorientowanego wykresu jako maksymalną nierównowagę cyklu. Teraz ${\ Displaystyle \ chi _ {c} (G)}$ jest minimalnym brakiem równowagi orientacji ${\ displaystyle G}$ .

Stosunkowo łatwo jest zauważyć, że ${\ Displaystyle \ chi _ {c} (G) \ równoważnik \ chi (G)}$ (zwłaszcza przy użyciu 1 lub 2), ale w rzeczywistości ${\ Displaystyle \ lceil \ chi _ {c} (G) \ rceil = \ chi (G)}$ . W tym sensie postrzegamy kołową liczbę chromatyczną jako udoskonalenie zwykłej liczby chromatycznej.

Kolorystyka kołowa została pierwotnie zdefiniowana przez Vince'a (1988) , który nazwał to „kolorowaniem gwiazd”.

Kolorystyka jest podwójna w stosunku do tematu przepływów nigdzie zerowych i rzeczywiście kolorowanie kołowe ma naturalne podwójne pojęcie: przepływy kołowe.

Wykresy kołowe pełne

Okrągły kompletny wykres
Wierzchołki	N
Krawędzie	n ( n - 2 k + 1) / 2
Obwód	${\ Displaystyle \ lewo \ {{\ rozpocząć {tablica} {ll} \ infty & n = 2 k \\ n & n = 2k+1\\4&2k+2\leq n<3k\\3&{\text{inaczej}}\end{array}}\right.}$
Liczba chromatyczna	⌈n/k⌉
Nieruchomości	( n - 2 k + 1) -regularny wierzchołek-przechodni okrężny hamiltonian
Notacja	${\ Displaystyle K_ {n/k}}$
Tabela wykresów i parametrów

Dla liczb całkowitych $}$$n$ pełny wykres ( jako a) $Displaystyle n \ geq 2k$ okrągła klika ) to wykres ze zbiorem wierzchołków ${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z} = \ {0,1, \ ldots, n -1\}}$ i krawędzie między elementami w odległości ${\ Displaystyle \ geq k.}$ To jest wierzchołek i sąsiaduje z:

${\ Displaystyle i + k, i + k + 1, \ ldots, ja + nk {\ bmod {n}}.}$

${\ Displaystyle K_ {n/1}}$ to tylko pełny wykres K _n , podczas gdy ${\ Displaystyle K_ {2n + 1/n}}$ to wykres cyklu ${\ Displaystyle C_ {2n + 1}.}$

Kolorowanie kołowe jest zatem, zgodnie z drugą definicją powyżej, homomorfizmem w pełny wykres kołowy. Kluczowym faktem dotyczącym tych wykresów jest to, że $c/d}}$ { $wtedy$ i tylko wtedy, $} {d}}.}$${\ Displaystyle {\ tfrac {a} {b }} = {\ tfrac {c} {d}}}$ To uzasadnia zapis, ponieważ jeśli za następnie ${\ Displaystyle K_ {a/b}}$ i $\ Displaystyle K_ {c/d}}$ są homomorficznie równoważne. Co więcej, porządek homomorfizmu wśród nich udoskonala porządek nadany przez pełne grafy do porządku gęstego , odpowiadającego liczbom wymiernym. ≥ $\ displaystyle \ geq 2}$ Na przykład

$\ do K_ {7/3}$

lub równoważnie

${\ Displaystyle K_ {2} \ do C_ {7} \ do C_ {5} \ do \ cdots \ do K_ {3} \ do K_ {4}\do \cdots}$

$odpowiadając$ rysunku można zinterpretować jako homomorfizm z snark J ₅ na K _5/2 ≈ do ₅ , który pojawia się wcześniej niż temu, że ${\ Displaystyle \ chi _ {c} (J_ {5}) \ równoważnik 2,5 <3.}$

Zobacz też

• Kolorowanie rang

•   Nadolski, Adam (2004), "Kołowe kolorowanie wykresów", Kolorowanie wykresów , Contemp. Matematyka, tom. 352, Providence, RI: Amer. Matematyka Soc., s. 123–137, doi : 10.1090/conm/352/09 , MR 2076994 .
•   Vince, A. (1988), „Numer chromatyczny gwiazdy”, Journal of Graph Theory , 12 (4): 551–559, doi : 10.1002/jgt.3190120411 , MR 0968751 .
•   Zhu, X. (2001), „Okrągła liczba chromatyczna, ankieta” , Matematyka dyskretna , 229 (1–3): 371–410, doi : 10.1016 / S0012-365X (00) 00217-X , MR 1815614 .