Раскраска заболеваемости

В теории графов , акт окраски обычно подразумевает назначение меток вершин , ребер или граней в графе . Частота окраска является специальной маркировкой график , где каждая частота ребра с вершиной назначается цветом при определенных ограничениях.

Определения [ править ]

Ниже G обозначает простой граф с непустым множеством вершин (непустым) V ( G ), множеством ребер E ( G ) и максимальной степенью ∆ ( G ).

Определение. Частота определяется как пара ( v , е ) , где является конечной точкой в простых словах, говорят , что вершина V падает на ребра е . Две инциденты ( v , e ) и ( u , f ) называются смежными или соседними, если выполняется одно из следующих условий:${\ Displaystyle v \ in V (G)}$${\ displaystyle e \ in E (G).}$

• v = u , e ≠ f
• е = е , v ≠ U
• e = { v , u }, f = { u , w } и v ≠ w .

Примеры соседних / соседних инцидентов. Знак * над ближайшим к вершине v ребром e обозначает инцидентность (v, e).

Определение. Пусть I ( G ) множество всех числа случаев G . Раскраска инцидентности G - это функция, которая принимает различные значения для смежных инцидентностей (мы используем упрощенное обозначение c ( v , u ) вместо c (( v , e )).) Минимальное количество цветов, необходимое для инцидентности. раскраска графа G известна как заболеваемость хроматического числа или частота окрашивания число из G , представленное${\ displaystyle c: I (G) \ to \ mathbb {N}}$${\displaystyle \chi _{i}(G).}$Это обозначение было введено Дженнифер Дж. Куинн Мэсси и Ричардом А. Бруальди в 1993 году.

Раскраска по инцидентности графа Петерсена

История [ править ]

Концепция раскраски инцидентности была введена Бруальди и Мэсси в 1993 году, которые ограничили ее в терминах Δ ( G ). Первоначально было обнаружено инцидентное хроматическое число деревьев, полных двудольных графов и полных графов. Они также предположили, что все графы могут иметь раскраску инцидентности с использованием Δ ( G ) + 2 цветов (гипотеза раскраски инцидентности - ICC). Эта гипотеза была опровергнута Гуидули, который показал, что концепция раскраски инцидентности представляет собой случай направленной звездчатости ^[1], введенный Алоном и Алгором. Его контрпример показал, что хроматическое число падения не превышает Δ ( G ) + O (log Δ ( G )). ^[2]

Chen et al. нашли частотное хроматическое число путей , вентиляторов, циклов , колес, полный трехсторонний граф и добавление граничных колес. Несколько лет спустя Shiu et al. показал, что эта гипотеза верна для некоторых кубических графов, таких как кубические гамильтоновы графы. Он показал, что в случае внешнепланарного графа максимальной степени 4, хроматическое число инцидентности не равно 5. В настоящее время выяснены границы для хроматического числа инцидентности различных классов графов.

Основные результаты [ править ]

Предложение. ${\displaystyle \chi _{i}(G)\geq \Delta (G)+1.}$

Доказательство. Пусть v вершина с максимальной степенью А в G . Пусть - ребра, инцидентные вершине v . Рассмотрим. Мы видим, что каждая пара Δ + 1 инцидентностей является соседней. Следовательно, эти инциденты должны быть окрашены разными цветами.${\displaystyle e_{1},e_{2},\ldots ,e_{\Delta }}$${\displaystyle e_{1}=\{v,w\}.}$${\displaystyle (v,e_{1}),(v,e_{2}),\ldots ,(v,e_{\Delta }),(w,e_{1})}$

Оценка достигается деревьями и полными графами:

• Если G - полный граф не менее чем с двумя вершинами, то${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$
• Если G - дерево по крайней мере с двумя вершинами, то${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

Основные результаты были доказаны Brualdi и Massey (1993). Шиу, Сун и Ву предложили некоторые необходимые условия для графа, удовлетворяющего${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• Хроматическое число инцидентности полного двудольного графа с m ≥ n ≥ 2 равно m + 2.${\displaystyle K_{m,n}}$
• ${\displaystyle \chi _{i}(C_{n})\leq 4}$ а также ${\displaystyle \chi _{i}(C_{3n})=3.}$

Раскраска инцидентности некоторых классов графов [ править ]

Сетки [ править ]

Введено несколько алгоритмов, обеспечивающих раскраску инцидентности сеток ^[3], таких как квадратные сетки , сотовые сетки и гексагональные сетки. Эти алгоритмы оптимальны. Для каждой сетки цвета инцидентности могут быть созданы за линейное время с наименьшим количеством цветов. Выяснилось, что для окраски углов квадратной, сотовой и гексагональной сеток требуется ∆ ( G ) + 1 цвет.

• Хроматическое число падения квадратной сетки равно 5.
• Хроматическое число угла падения гексагональной сетки равно 7.
• Хроматическое число падения ячеистой сетки - 4.

Графики Халина [ править ]

Чен, Ван и Панг доказали, что если G - граф Халина с ∆ ( G )> 4, то для графов Халина с ∆ ( G ) = 3 или 4, Цзин-Чжэ Цюй оказался равным 5 или 6 соответственно. Вопрос о том, равно ли число инцидентной раскраски графов Халина с низкой степенью Δ ( G ) + 1, остается нерешенным.${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$${\displaystyle \chi _{i}(G)}$

Шиу и Сун доказали, что каждый кубический граф Халина, кроме того, имеет раскраску инцидентности в Δ ( G ) + 2 цвета. Су, Мэн и Го распространили этот результат на все графы псевдохалина.${\displaystyle K_{4}}$

Если граф Халина G содержит дерево T , то ^[4]${\displaystyle \chi _{i}(G^{2})\leq \Delta (T^{2})+\Delta (T)+8.}$

k-вырожденные графы [ править ]

DL Chen, PCB Lam и WC Shiu предположили, что инцидентное хроматическое число кубического графа G не превосходит ∆ ( G ) + 2. Они доказали это для некоторых кубических графов, таких как гамильтоновы кубические графы. Основываясь на этих результатах, М. Х. Долама, Э. Сопена и X. Чжу (2004) изучили классы графов, для которых ограничено ∆ ( G ) + c, где c - некоторая фиксированная константа. ^[5] Граф называется к -порожденной , если для каждого подграфа H из G , минимальная степень Н не превосходит к .${\displaystyle \chi _{i}(G)}$

• Хроматическое число инцидентности k -вырожденных графов G не превосходит ∆ ( G ) + 2 k - 1.
• Хроматическое число инцидентности K ₄ минорных свободных графов G не превосходит ∆ ( G ) + 2 и образует жесткую границу.
• Хроматическое число инцидентности плоского графа G не превосходит ∆ ( G ) + 7.

Внешнепланарные графики [ править ]

Рассмотрим Внешнепланарные граф G с вырезать вершины V такой , что G - v является объединением из и . Пусть (соответственно ) - индуцированный подграф на вершине v и вершинах (соответственно ). Тогда это максимум , и где есть степень вершины V в G .${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle \chi _{i}(G)}$${\displaystyle \chi _{i}(G_{1}),\chi _{i}(G_{2})}$${\displaystyle 1+d_{G}(v)}$${\displaystyle d_{G}(v)}$

Хроматическое число инцидентности внешнепланарного графа G не превосходит ∆ ( G ) + 2. В случае внешнепланарных графов с ∆ ( G )> 3 хроматическое число инцидентности равно ∆ ( G ) + 1.

Поскольку внешнепланарные графы являются K ₄ -графиками без миноров, они допускают (∆ + 2, 2) -сходную раскраску. ^{[5] [6]} Решение для хроматического числа инцидентности внешнепланарного графа G, имеющего Δ ( G ) = 3 и 2-связного внешнепланарного графа, все еще остается открытым вопросом.

Хордовые кольца [ править ]

Хордовые кольца - разновидности кольцевых сетей. Использование хордовых колец в коммуникации очень широко из-за их преимуществ перед сетями взаимосвязей с кольцевой топологией и другими анализируемыми структурами, такими как сетки, гиперкубы, графы Кэли и т. Д. Арден и Ли ^[7] впервые предложили хордовое кольцо степени 3. , то есть сеть с кольцевой структурой, в которой каждый узел имеет дополнительную связь, известную как хорда, с каким-либо другим узлом в сети. Распределенные петлевые сети - это хордовые кольца степени 4, которые строятся путем добавления 2 дополнительных хорд в каждую вершину кольцевой сети.

Хордовое кольцо на N узлах и длине хорды d , обозначенное CR ( N , d ), представляет собой граф, определяемый как:

${\displaystyle {\begin{aligned}V(G)&=\{v_{0},v_{1},\ldots ,v_{N-1}\}\\E(G)&=\{v_{i}v_{j}:i-j\equiv 1,d{\bmod {N}}\}\end{aligned}}}$

Эти графики изучаются в связи с их применением в общении. Кунг-фу Дин, Кунг-Джуй Пай и Ро-Ю Ву изучали инцидентную окраску хордовых колец. ^[8] Сформулировано несколько алгоритмов для нахождения хроматического числа инцидентности хордовых колец. Основные выводы:

${\displaystyle {\begin{aligned}\chi _{i}(CR(N,2))&={\begin{cases}5&5|N\\6&{\text{otherwise}}\end{cases}}\\\chi _{i}(CR(N,3))&={\begin{cases}5&5|N\\6&N\equiv 2{\bmod {5}}\end{cases}}\end{aligned}}}$

Степени циклов [ править ]

Кейцуда Накпрасит и Киттикорн Накпрасит изучали раскраску инцидентности степеней циклов. Если 2 k + 1 ≥ n, то предположим, что n > 2 k + 1, и напишем:${\displaystyle C_{n}^{k}.}$${\displaystyle C_{n}^{k}=K_{n}}$

${\displaystyle n=(2k+1)t+r,\quad 1\leq t,\quad 0\leq r\leq 2k.}$

Их результаты можно резюмировать следующим образом: ^[9]

${\displaystyle {\begin{aligned}\chi _{i}(C_{n}^{k})&={\begin{cases}2k+1&r=0\\2k+2&1\leq r\leq t{\text{ or }}r=2k\end{cases}}&&k\geq 3\\\chi _{i}(C_{n}^{2})&={\begin{cases}5&5|n\\6&{\text{otherwise}}\end{cases}}\end{aligned}}}$

Связь с гипотезой о раскраске инцидентности дается наблюдением, что ${\displaystyle \Delta (C_{n}^{k})=2k.}$

Связь между хроматическим числом инцидентности и числом доминирования на графике [ править ]

Предложение. ^[10] Пусть G - простой связный граф порядка n , размера m и числа доминирования. Тогда${\displaystyle \gamma .}$${\displaystyle \chi _{i}(G)\geq {\tfrac {2m}{n-\gamma }}.}$

Доказательство. Сформируйте орграф D ( G ) из графа G , разделив каждое ребро G на 2 дуги в противоположных направлениях. Мы видим, что общее количество дуг в D ( G ) равно 2 м . Согласно Guiduli, ^[2] частота окраска G эквивалентна правильной окраске орграфа D ( G ), где 2 различных дуг и являются смежными , если одно из следующих условий: (я) у = х ; (ii) v = x или y =${\displaystyle {\overrightarrow {uv}}}$${\displaystyle {\overrightarrow {xy}}}$u . По определению смежности дуг независимый набор дуг в D ( G ) является звездным лесом. Следовательно, максимальный независимый набор дуг - это максимальный звездный лес . Это означает, что требуются как минимум классы цветов. ^[10]${\displaystyle {\tfrac {2m}{n-\gamma }}}$

Это соотношение широко использовалось при характеризации раскрашиваемых r -регулярных графов с ( r + 1) -согласованием . Главный результат о раскраске инцидентности r -регулярных графов: если граф G является r-регулярным графом , то тогда и только тогда, когда V ( G ) является несвязным объединением r + 1 доминирующих множеств . ^[10]${\displaystyle \chi _{i}(G)=\chi _{i}(G^{2})=r+1}$

Раскраска интервальной заболеваемости [ править ]

Определение. Конечное подмножество является интервалом тогда и только тогда, когда оно содержит все числа от минимума до максимума.${\displaystyle A\subset \mathbb {N} }$

Определение. Пусть c - раскраска инцидентности группы G, и определим

${\displaystyle A_{c}(v)=\{c(v,e):(v,e)\in I(G)\}.}$

Интервал частота раскраски из G является частота окрашивания с таким образом, что для каждой вершины V из G множество представляет собой интервал. ^{[11] [12]} интервал частота окрашивания число из G минимальное число цветов , используемых для интервала падения окраска G . Обозначается он. Понятно, что если для раскраски интервальной инцидентности используются только цвета, то она называется минимальной.${\displaystyle A_{c}(v)}$${\displaystyle \chi _{ii}.}$${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).}$${\displaystyle \chi _{ii}}$

Концепция интервальной раскраски инцидентности была введена А. Малафейской, Р. Янчевским и М. Малафейским. Они доказаны для двудольных графов. ^[13] В случае регулярных двудольных графов равенство выполняется. Подкубические двудольные графы допускают интервальную раскраску инцидентности в четыре, пять или шесть цветов. Они также доказали, что инцидентная 5-раскрашиваемость может быть решена за линейное время для двудольных графов с ∆ ( G ) = 4.${\displaystyle \chi _{ii}(G)\leq \Delta (G)}$

Раскраска дробной заболеваемости [ править ]

Дробная версия раскраски инцидентности была впервые введена Янгом в 2007 году. K -раскраска случайности r- кратности графа G - это присвоение r цветов каждой инцидентности графа G из набора k цветов таким образом, что смежные инцидентности даны непересекающиеся наборы цветов. ^[14] По определению очевидно, что k- раскраска инцидентности из одного кортежа также является k- раскраской инцидентности .

Хроматическое число дробной инцидентности графа G - это нижняя грань дробей таким образом, что G допускает k- раскраску с r- кратной инцидентностью . Раскраска по дробной частоте имеет большое применение в нескольких областях информатики. Основываясь на результатах раскраски инцидентности, проведенных Гуидули, ^[2] Ян доказал, что хроматическое число дробной инцидентности любого графа не превосходит Δ ( G ) + 20 log Δ ( G ) + 84. Он также доказал существование графов с дробным числом хроматическое число падения не менее Δ ( G ) + Ω (log Δ ( G )).${\displaystyle {\tfrac {k}{r}}}$

Неравенство Нордхауса – Гаддама [ править ]

Пусть G граф с п вершинами, где обозначает дополнение G . Тогда ^[10] Эти оценки точны для всех значений n .${\displaystyle G\neq K_{n},{\overline {K_{n}}}}$${\displaystyle {\overline {G}}}$${\displaystyle n+2\leq \chi _{i}(G)+\chi _{i}({\overline {G}})\leq 2n-1.}$

Игра-раскраска по заболеваемости [ править ]

Игра-раскраска по инцидентам была впервые представлена ​​SD Andres. ^[15] Это инцидентная версия игры-раскраски вершин, в которой инциденты графа раскрашиваются вместо вершин. Хроматическое число инцидентности в игре - это новый параметр, определяемый как теоретико-игровой аналог хроматического числа инцидентности.

Игра состоит в том, что два игрока, Алиса и Боб, создают правильную раскраску инцидентности. Правила изложены ниже:

• Алиса и Боб раскрашивают инцидентности графа G набором k цветов.
• Они по очереди обеспечивают правильную окраску неокрашенному инциденту. В общем, начинается Алиса.
• В случае инцидента, который не может быть раскрашен должным образом, выигрывает Боб.
• Если все инциденты на графике раскрашены должным образом, Алиса выигрывает.

Хроматическое число случайной игры графа G , обозначенное как , - это наименьшее количество цветов, необходимое Алисе для победы в игре-раскраске по инцидентности. Он объединяет идеи случайного хроматического числа графа и игрового хроматического числа в случае неориентированного графа. Андрес выяснил , что верхняя граница для в случае K -degenerate графов 2Д + 4 K - 2. Эта оценка была улучшена до 2б + 3 к - 1 в случае графов , в которых Δ составляет по меньшей мере 5 к . Также определяется хроматическое число звездочек, циклов и достаточно больших колес в игре на случайность. ^[15]${\displaystyle i_{g}(G)}$${\displaystyle i_{g}(G)}$Джон Ю. Ким (2011) обнаружил точное хроматическое число больших путей в игре с инцидентами и дал правильное доказательство результата, сформулированного Андресом относительно точного хроматического числа больших колес в игре с инцидентами. ^[16]

Ссылки [ править ]