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

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

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

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

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

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

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

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

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

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

${\displaystyle K_{n/1}}$— это просто полный граф K _n , а — это циклический граф ${\displaystyle K_{2n+1/n}}$ ${\displaystyle C_{2n+1}.}$

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

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

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

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

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

Смотрите также

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

Ссылки

• Надольски, Адам (2004), «Круговая раскраска графов», Раскраски графов , Contemp. Math., т. 352, Провиденс, Род-Айленд: Amer. Math. 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.
• Чжу, С. (2001), «Круговое хроматическое число, обзор», Дискретная математика , 229 (1–3): 371–410, doi :10.1016/S0012-365X(00)00217-X, MR  1815614.