Раскраска инцидентности

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

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

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

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

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

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

Чен и др. нашли хроматическое число инцидентности путей , вееров, циклов , колес, полного трехдольного графа и колес добавления ребер. Несколько лет спустя Шиу и др. показали, что эта гипотеза верна для некоторых кубических графов, таких как кубические гамильтоновы графы. Он показал, что в случае внешнепланарного графа максимальной степени 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.}$

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

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• Хроматическое число инцидентности полного двудольного графа с m ≥ n ≥ 2 равно m + 2.${\displaystyle K_{м,н}}$
• ${\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 Цзин-Чжэ Цюй показал , что ∆( G ) = 5 или 6 соответственно. Является ли число инцидентной раскраски графов Халина с низкой степенью ∆( G ) + 1, все еще остается нерешенной проблемой.${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$${\displaystyle \chi _{i}(G)}$

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

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

DL Chen, PCB Lam и WC Shiu предположили, что хроматическое число инцидентности кубического графа G не превышает ∆( G ) + 2. Они доказали это для некоторых кубических графов, таких как гамильтоновы кубические графы. Основываясь на этих результатах, MH Dolama, E. Sopena и X. Zhu (2004) изучили классы графов, для которых ограничено ∆( G ) + c , где c — некоторая фиксированная константа. ^[5] Граф называется k -порожденным, если для каждого подграфа H графа G минимальная степень H не превышает k .${\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.

Поскольку внешнепланарные графы являются графами, свободными от K4 _- миноров, они допускают раскраску инцидентности (Δ + 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}:ij\equiv 1,d{\bmod {N}}\}\end{aligned}}}$

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

${\displaystyle {\begin{align}\chi _{i}(CR(N,2))&={\begin{cases}5&5|N\\6&{\text{иначе}}\end{cases}}\\\chi _{i}(CR(N,3))&={\begin{cases}5&5|N\\6&N\equiv 2{\bmod {5}}\end{cases}}\end{align}}}$

Кейтсуда Накпрасит и Киттикорн Накпрасит изучали инцидентную раскраску степеней циклов. Если 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{align}\chi _{i}(C_{n}^{k})&={\begin{cases}2k+1&r=0\\2k+2&1\leq r\leq t{\text{ или }}r=2k\end{cases}}&&k\geq 3\\\chi _{i}(C_{n}^{2})&={\begin{cases}5&5|n\\6&{\text{иначе}}\end{cases}}\end{align}}}$

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

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

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

Это отношение широко использовалось в характеристике ( r + 1)-инцидентно раскрашиваемых r -регулярных графов. Основной результат по инцидентной раскраске 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 — это раскраска инцидентности c, такая что для каждой вершины 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 году. r -кортежная инцидентная k -раскраска графа G — это назначение r цветов каждому инциденту графа G из набора из k цветов таким образом, что соседним инцидентностям задаются непересекающиеся наборы цветов. ^[14] По определению очевидно, что 1-кортежная инцидентная k- раскраска также является инцидентной k -раскраской.

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

Пусть G — граф с n вершинами, такой что где обозначает дополнение к 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 -вырожденных графов равна 2Δ + 4 k − 2. Эта граница была улучшена до 2Δ + 3 k − 1 в случае графов, в которых Δ равно по крайней мере 5 k . Также определены хроматическое число игры инцидентности звезд, циклов и достаточно больших колес. ^[15] Джон И. Ким (2011) выяснил точное хроматическое число игры инцидентности больших путей и дал правильное доказательство результата, заявленного Андресом относительно точного хроматического числа игры инцидентности больших колес. ^[16]${\displaystyle i_{g}(G)}$${\displaystyle i_{g}(G)}$

• L(h, k)-раскраска
• Гармоничный колорит
• Звездная раскраска
• Полная окраска
• Круговая раскраска
• Раскрашивание путей
• Дефектная окраска
• Радиораскраска
• Ациклическая окраска