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

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

Определения

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

Определение. Инцидентность определяется как пара ( v , e ), где — конечная точка Проще говоря, говорят, что вершина v инцидентна ребру e . Два инцидента ( v , e ) и ( u , f ) называются смежными или соседними , если выполняется одно из следующих условий: $v\in V(G)$ $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 году. $c:I(G)\to \mathbb {N}$ $\chi _{i}(G).$

История

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

Чен и др. нашли хроматическое число инцидентности путей , вееров, циклов , колес, полного трехдольного графа и колес добавления ребер. Несколько лет спустя Шиу и др. показали, что эта гипотеза верна для некоторых кубических графов, таких как кубические гамильтоновы графы. Он показал, что в случае внешнепланарного графа максимальной степени 4 хроматическое число инцидентности не равно 5. Границы хроматического числа инцидентности различных классов графов теперь найдены.

Основные результаты

Предложение.

\chi _{i}(G)\geq \Delta (G)+1.

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

Граница достигается с помощью деревьев и полных графов:

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

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

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

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

Сетки

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

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

Графики Халина

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

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

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

k-вырожденные графы

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 . $\chi _{i}(G)$

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

Внешнепланарные графы

Рассмотрим внешнепланарный граф G с вершиной разреза v такой, что G – v является объединением и . Пусть (соотв. ) — индуцированный подграф на вершине v и вершинах (соотв. ). Тогда — максимум и где — степень вершины v в G . $H_{1}$ $H_{2}$ $G_{1}$ $G_{2}$ $H_{1}$ $H_{2}$ $\chi _{i}(G)$ $\chi _{i}(G_{1}),\chi _{i}(G_{2})$ $1+d_{G}(v)$ $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 ), представляет собой граф, определяемый как:

{\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] Сформулировано несколько алгоритмов для нахождения хроматического числа инцидентности хордовых колец. Основные выводы:

{\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 и запишем: $C_{n}^{k}.$ $C_{n}^{k}=K_{n}$

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

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

{\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}}

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

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

Предложение. ^[10] Пусть G — простой связный граф порядка n , размера m и числа доминирования . Тогда

\гамма .

\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] ${\overrightarrow {uv}}$ ${\overrightarrow {xy}}$ ${\tfrac {2m}{n-\gamma }}$

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

Интервальная окраска инцидентности

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

Определение. Пусть c — инцидентная раскраска графа G и определим

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

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

Концепция интервальной инцидентной раскраски была введена А. Малафейской, Р. Янчевским и М. Малафейским. Они доказали это для двудольных графов. ^[13] В случае регулярных двудольных графов равенство имеет место. Субкубические двудольные графы допускают интервальную инцидентную раскраску с использованием четырех, пяти или шести цветов. Они также доказали, что инцидентная 5-раскрашиваемость может быть определена за линейное время для двудольных графов с ∆( G ) = 4. $\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 )). ${\tfrac {k}{r}}$

Неравенство Нордхауза–Гаддума

Пусть G — граф с n вершинами, такой что где обозначает дополнение к G. Тогда ^[10] Эти границы точны для всех значений n . $G\neq K_{n},{\overline {K_{n}}}$ ${\overline {G}}$ $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] $i_{g}(G)$ $i_{g}(G)$

Ссылки

^ Алгор И., Алон Н. (1989); «Звездная древовидность графов», Дискретная математика 75, стр. 11-22.
^ abc Guiduli B. (1997); «О раскраске инцидентности и звездной древовидности графов», Discrete Mathematics 163, стр. 275-278
^ Хуан, CI; Ван, YL; Чунг, SS (2004), «Числа инцидентной раскраски сеток», Компьютеры и математика с приложениями 48, стр. 1643–1649
^ Ван, SD; Ченг, DL; Пан, SC (2002), «Число инцидентной раскраски графов Халина и внешнепланарных графов», Дискретная математика 256, стр. 397–405
^ ab Хоссейни Долама, М.; Сопена, Э.; Чжу, X. (2004), «Раскраска инцидентности k-генерированных графов», Дискретная математика 283, стр. 121–128
^ Ван, С.; Сюй, Дж.; Ма, Ф.; Сюй, К. (2008), «(Δ + 2, 2)-инцидентная раскраска внешнепланарных графов», Progress in Natural Science 18, стр. 575–578.
^ Арден Б. В., Ли Х. (1981); «Анализ сети хордовых колец», IEEE Transactions on Computers 30, стр. 291-295.
^ Дин КФ, Пай КДж, Ю Р. (1981); «Некоторые результаты по числу инцидентной раскраски хордовых колец*», 32-й семинар по комбинаторной математике и теории вычислений, стр. 89-93.
^ Накпрасит, Кейтсуда и Накпрасит, Киттикорн (2012), «Раскраска инцидентности степеней циклов», Международный журнал чистой и прикладной математики 76(1), стр. 143–148
^ abcd Sun, PK (2012), «Раскраска инцидентности регулярных графов и дополнительных графов», Taiwanese Journal of Mathematics 16, № 6, стр. 2289–2295
^ Janczewski, R.; Malafiejska, A.; Malafiejski, M., «Назначение интервальной длины волны в полностью оптических звездных сетях», Parallel Processing and Applied Mathematics, 8-я международная конференция, PPAM 2009, Втроцлав, Польша, 13–16 сентября 2009 г. Revised Selected Papers Part I (Springer), стр. 11–20, doi:10.1007/978-3-642-14390-8_2, ISBN 978-3-642-14389-2
^ Янчевский, Р.; Малафейская, А.; Малафейский, М. (2015), «Раскраска графа инцидентности интервалов», Дискретная прикладная математика 182, стр. 73–83
^ Янчевский, Р.; Малафейская, А.; Малафейский, М. (2014), «Интервальная раскраска инцидентности двудольных графов», Дискретная прикладная математика 166, стр. 131–145
^ Янг, Д (2012), «Дробная инцидентная раскраска и звездная древовидность графов», Ars Combinatoria - Ватерлоо, затем Виннипег 105, стр. 213–224
^ ab Андрес, SD (2009), «Игра инцидентности хроматического числа», Дискретная прикладная математика 157, стр. 1980–1987
^ Ким, JY (2011), «Игра инцидентности хроматического числа путей и подграфов колес», Дискретная прикладная математика 159, стр. 683–694

Дополнительные ссылки

Майданский, М. (2005), «Гипотеза о раскраске инцидентности для графов максимальной степени 3», Дискретная математика , т. 292, стр. 131–141.
Хартке, СГ; Хеллелоид, ГТ (2012), «Реконструкция графа по его графу инцидентности дуг», Графы и комбинаторика , т. 28, стр. 637–652, doi :10.1007/s00373-011-1073-7, S2CID 14656326.
Сан, ПК; Шиу, ВК (2012), «Недействительные доказательства инцидентной раскраски» (PDF) , Дискретная математика , т. 54, стр. 107–114.
Ли, Д.; Лю, М. (2008), «Раскраска инцидентности квадратов некоторых графов», Дискретная математика , т. 308, стр. 6575–6580.
Бонами, М.; Хоквард, Х.; Керджоудж, С.; Распо, А. (2015), Раскраска инцидентности графов с высокой максимальной средней степенью , arXiv : 1412.6803 , Bibcode : 2014arXiv1412.6803B.
Хоссейни Долама, М.; Сопена, Э. (2005), «О максимальной средней степени и хроматическом числе инцидентности графа» (PDF) , Дискретная математика и теоретическая информатика , т. 7, стр. 203–216.
Shiu, WC; Lam, PCP; Chen, DL (2002), «О раскраске инцидентности для некоторых кубических графов», Discrete Mathematics, т. 252, стр. 259–266, doi :10.1016/S0012-365X(01)00457-5.
Накпрасит, К. (2014), «Сильный хроматический индекс графов и подразделений», Дискретная математика , т. 317, стр. 75–78.
Ding, KF; Pai, K. J; Chang, JM; Tsaur, R. (2015), "Некоторые результаты инцидентной раскраски обобщенных графов Петерсена", Intelligent Systems and Applications: Proceedings of the International Computer Symposium (ICS), состоявшегося в Тайчжуне, Тайвань, 12–14 декабря 2014 г., том 274, IOS Press, стр. 85–91, doi :10.3233/978-1-61499-484-8-85.
Лян, Л.; Гао, В. (2010), «О дробном хроматическом числе инцидентности обобщенного тета-графа», Журнал Чунцинского педагогического университета , т. 27, стр. 36–39.
Shiu, WC; Lam, PCB; Chen, DL (2002), «Заметка о раскраске инцидентности для некоторых кубических графов», Discrete Mathematics , т. 252, стр. 259–266.
Сан, ПК; Шиу, ВК (2012), «Некоторые результаты по окраске инцидентности, древовидности звезд и числу доминирования» (PDF) , Australasian Journal of Combinitorics , т. 54, стр. 107–114.
Ву, Дж. (2009), «Некоторые результаты о числе инцидентной раскраски графа», Дискретная математика , т. 309, стр. 3866–3870.
Ли, С.; Ту, Дж. (2008), «NP-полнота 4-инцидентной раскрашиваемости полукубических графов», Дискретная математика , т. 308, стр. 1334–1340.
Пай, К. Дж.; Чанг, Дж. М.; Ву, Р. Ю. (2014), «Раскраска инцидентности на гиперкубах», Теоретическая информатика , т. 557, стр. 59–65.
Пай, К. Дж.; Чанг, Дж. М.; Ву, Р. Ю. (2014), «О числе инцидентной раскраски сложенных гиперкубов», Труды 18-й Международной конференции по компьютерным наукам и технике (ICSEC 2014), 30 июля - 1 августа, Кхонкэн, Таиланд , стр. 7–11.
Sopena, É.; Wu, J (2013), "Хроматическое число инцидентности тороидальных сеток", Discussiones Mathematicae Graph Theory , 33 (2): 315–327, arXiv : 0907.3801 , doi : 10.7151/dmgt.1663, S2CID 1313615.
Андрес, SD (2009). "Исправление к: Инцидентная игра хроматического числа". Дискретная прикладная математика . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
Шарпантье, К.; Сопена, Э. (2015), «Хроматическое число игры инцидентности (a,d)-разложимых графов», Журнал дискретных алгоритмов , т. 31, стр. 14–25.
Wu, J.; Zhu, X. (2008), «6-релаксированная игра хроматического числа внешнепланарных графов», Discrete Mathematics , 308 (24): 5974–5980, doi : 10.1016/j.disc.2007.11.015.
Meng, X.; Guo, J.; Su, B. (2012), «Раскраска инцидентности псевдографов Халина», Discrete Mathematics , 312 (22): 3276–3282, doi :10.1016/j.disc.2012.07.024.
Андрес, СД (2009), «Легкость орграфов на поверхностях и направленное игровое хроматическое число», Дискретная математика , т. 309, стр. 3564–3579.
Ли, С.; Ту, Дж. (2008), «NP-полнота 4-инцидентной раскрашиваемости полукубических графов», Дискретная математика , 308 (7): 1334–1340, arXiv : math/0607071 , doi : 10.1016/j.disc.2007.03.076, S2CID 59464.
Чжу, С. (1999), «Игра раскраски числа планарных графов», Журнал комбинаторной теории, Серия B , 75 (2): 245–258, doi : 10.1006/jctb.1998.1878.
Лю, С.; Ли, И. (2005), «Хроматическое число инцидентности некоторого графа», Международный журнал математики и математических наук , 1 (5): 803–813, doi : 10.1155/IJMMS.2005.803.
Dong, GX; Liu, XF (2014), «Число инцидентной раскраски некоторых графов соединений», Applied Mechanics and Materials , 602–605: 3185–3188, doi :10.4028/www.scientific.net/AMM.602-605.3185, S2CID 122567953.