Круговая окраска - Circular coloring

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

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

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

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

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

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

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

Круговой полный график
Вершины	п
Края	п(п − 2k + 1) / 2
Обхват	${displaystyle left {{egin {array} {ll} infty & n = 2k n & n = 2k + 1 4 & 2k + 2leq n <3k 3 & {ext {else}} end {array}} ight.}$
Хроматическое число	⌈N / k⌉
Характеристики	(п − 2k + 1)-обычный Вершинно-транзитивный Циркулянт Гамильтониан
Обозначение	${displaystyle K_ {n / k}}$
Таблица графиков и параметров

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

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

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

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

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

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

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

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

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

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

Рекомендации

• Надольски, Адам (2004), "Круговая раскраска графов", Раскраски графиков, Contemp. Математика, 352, Провиденс, Род-Айленд: амер. Математика. Soc., Стр. 123–137, Дои:10.1090 / conm / 352/09, МИСТЕР  2076994.
• Винс, А. (1988), "Хроматическое число звезды", Журнал теории графов, 12 (4): 551–559, Дои:10.1002 / jgt.3190120411, МИСТЕР  0968751.
• Чжу, X. (2001), "Круговое хроматическое число, обзор", Дискретная математика, 229 (1–3): 371–410, Дои:10.1016 / S0012-365X (00) 00217-X, МИСТЕР  1815614.

Этот комбинаторика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.