Круговая раскраска

Хроматическое число цветочного снарка J ₅ равно 3, а круговое хроматическое число ≤ 5/2.

В теории графов круговая раскраска — это разновидность раскраски, которую можно рассматривать как усовершенствование обычной раскраски графов . Круговое хроматическое число графа $G$, обозначенный $\chi _{c}(G)$ может быть задано любым из следующих определений, все из которых эквивалентны (для конечных графов).

1. $\chi _{c}(G)$ является нижней границей всех действительных чисел $r$ так что существует карта из $V(G)$ к кругу окружности 1 со свойством, что любые две соседние вершины отображаются в точки на расстоянии $\geq {\tfrac {1}{r}}$ по этому кругу.
2. $\chi _{c}(G)$ это нижняя грань всех рациональных чисел ${\tfrac {n}{k}}$ так что существует карта из $V(G)$ в циклическую группу $\mathbb {Z} /n\mathbb {Z}$ со свойством, что соседние вершины сопоставляются с элементами на расстоянии $\geq k$ отдельно.
3. В ориентированном графе объявите дисбаланс цикла $C$ быть $|E(C)|$ разделенное на минимальное количество ребер, направленных по часовой стрелке, и количество ребер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа как максимальный дисбаланс цикла. Сейчас, $\chi _{c}(G)$ – минимальный дисбаланс ориентации $G$.

Сравнительно легко увидеть, что $\chi _{c}(G)\leq \chi (G)$ (особенно при использовании 1 или 2), но на самом деле $\lceil \chi _{c}(G)\rceil =\chi (G)$. Именно в этом смысле мы рассматриваем круговое хроматическое число как уточнение обычного хроматического числа.

Круговая окраска была первоначально определена Винсом (1988) , который назвал ее «звездной окраской».

Раскраска двойственна теме потоков нигде ненулевых , и действительно, круговая раскраска имеет естественное двойственное понятие: круговые потоки.

Круговые полные графики

Круговой полный граф
Вершины	н
Края	п ( п - 2 к + 1)/2
Обхват	$\left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{otherwise}}\end{array}}\right.$
Хроматическое число	⌈n/k⌉
Характеристики	( n − 2 k + 1) -регулярный Вершинно-транзитивный циркулирующий гамильтониан
Обозначения	$K_{n/k}$
Таблица графиков и параметров

Для целых чисел $n,k$ такой, что $n\geq 2k$, полный круговой граф $K_{n/k}$ (также известный как круговая клика ) — это граф с множеством вершин $\mathbb {Z} /n\mathbb {Z} =\{0,1,\ldots ,n-1\}$ и края между элементами на расстоянии $\geq k.$Это вершина i, примыкающая к:

$i+k,i+k+1,\ldots ,i+n-k{\bmod {n}}.$

$K_{n/1}$ представляет собой полный граф K _n , а $K_{2n+1/n}$ это график цикла $C_{2n+1}.$

Тогда круговая раскраска, согласно второму определению выше, является гомоморфизмом полного кругового графа. Важнейшим фактом в отношении этих графиков является то, что $K_{a/b}$ допускает гомоморфизм в $K_{c/d}$ тогда и только тогда, когда ${\tfrac {a}{b}}\leq {\tfrac {c}{d}}.$ Это оправдывает обозначения, так как если ${\tfrac {a}{b}}={\tfrac {c}{d}}$ затем $K_{a/b}$ и $K_{c/d}$ гомоморфно эквивалентны. Более того, порядок гомоморфизма среди них уточняет порядок, заданный полными графами, до плотного порядка , соответствующего рациональным числам. $\geq 2$. Например

$K_{2/1}\to K_{7/3}\to K_{5/2}\to \cdots \to K_{3/1}\to K_{4/1}\to \cdots$

или эквивалентно

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

Пример на рисунке можно интерпретировать как гомоморфизм цветочной снарки J ₅ в K _5/2 ≈ C ₅ , который наступает раньше, чем $K_{3}$ соответствует тому факту, что $\chi _{c}(J_{5})\leq 2.5<3.$

См. также

• Раскраска рангов

Ссылки

• Надольски, Адам (2004), «Круговая раскраска графов», Раскраски графов , Contemp. Матем., вып. 352, Провиденс, Род-Айленд: Амер. Математика. Soc., стр. 123–137, doi : 10.1090/conm/352/09 , ISBN.  978-0-8218-3458-9 , МР   2076994 .
• Винс, А. (1988), «Звездное хроматическое число», Журнал теории графов , 12 (4): 551–559, doi : 10.1002/jgt.3190120411 , MR   0968751 .
• Чжу, X. (2001), «Круговое хроматическое число, обзор», Discrete Mathematics , 229 (1–3): 371–410, doi : 10.1016/S0012-365X(00)00217-X , MR   1815614 .