Круговая окраска - 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=2k+14&2k+2leq n<3k3&{ ext{otherwise}}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.