Интервальная окраска края - Interval edge coloring

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

История

Концепция чего-либо последовательная окраска краев был введен с терминологией 'раскраска края интервала ' Асратяна и Камаляна в 1987 г. в статье «Интервальные раскраски ребер мультиграфа».^[1] С тех пор как была введена интервальная раскраска ребер графов, математики изучали существование интервальных раскрашиваемых ребер графов, поскольку не все графы допускают интервальную раскраску ребер. Простое семейство графов, которое допускает раскраску ребер интервалов, представляет собой полный граф четного порядка, а контрпример семейства графов включает полные графы нечетного порядка. Наименьший граф, который не допускает интервальной раскраски. Существуют даже графы с 28 вершинами и максимальной степенью 21, которые не могут быть интервально раскрашены Севастьяновым, хотя интервальная раскрашиваемость графов с максимальной степенью, лежащей между четырьмя и двенадцатью, пока неизвестна.

Асратян и Камалян (1987) доказал, что если граф является интервально раскрашиваемым, то хроматическое число ребер меньше или равно на единицу меньше, чем число его вершин, а также отметил, что если G r-регулярен, то G имеет интервальную раскраску тогда и только тогда, когда G имеет правильная раскраска r-ребра.^[1]

Раскраска ребер интервалов исследуется в регулярных графах, двудольных графах, которые являются регулярными, а не регулярными, планарными графами, среди других расширений, которые были инициированы в раскраске ребер интервалов.

Определение

Позволять г - простой интервальный граф. Раскраска ребер графа G в цвета 1, 2,. . . , т называется «интервальной t-раскраской», если для каждого я ∈ {1, 2, . . . , т} есть хотя бы один край г окрашенный я и цвета ребер, инцидентных любой вершине г различны и образуют интервал целых чисел.^[2] В качестве альтернативы раскраска ребер интервала определяется как: раскраска ребер графа. г с цветами 1.. . т является 'интервал t-раскраски ' если используются все цвета и цвета ребер, инцидентных каждой вершине г различны и образуют интервал целых чисел. График г является "раскрашиваемым интервалом", если г имеет интервальную t-раскраску для некоторого положительного целого числа т. Позволять N - множество всех интервальных раскрашиваемых графов. Для графика г ∈ N, наименьшее и наибольшее значения т для которого г имеет интервал т-краски обозначаются ш(г) и W(г), соответственно. Интервальная раскраска ребер графа называется равномерной интервальной раскраской ребер, если любые два цветовых класса графа отличаются не более чем на единицу.

Набор цветов ребер, инцидентных вершине (x), называется спектром (Икс). Мы говорим, что подмножество р вершин г имеет я-собственность, если есть правильный край т-крашивание г что интервал над р.

Несколько результатов

Если граф без треугольников G = (V, E) имеет интервальную t-раскраску, тогда t ≤ | V | −1. Асратян и Камалян доказали, что если G интервально раскрашиваема, то χ '(G) = ∆ (G).^[1][3]

Петросян исследовал интервальные раскраски полных графов и n-мерных кубов и показал, что если n ⩽ t ⩽ n (n + 1) / 2, то n-мерный куб Qn имеет интервальную t-раскраску.^[2] Аксенович доказал, что все внешнепланарные триангуляции с более чем тремя вершинами и без разделяющих треугольников можно раскрашивать по интервалам.^[4] Если г является регулярным графом w (G) = ∆ (G) и G имеет интервальную t-раскраску для любого t, w (G) ≤ t ≤ W (G).

Интервальная 5-раскраска K₆

Интервальная раскраска ребер полного графа^[2]

• Полный граф является интервально раскрашиваемым тогда и только тогда, когда число его вершин четное.
• Если n =_п2^q, где p нечетно, q неотрицательно и 2n − 1≤t≤4n − 2 − p − q, то полный граф K_2n имеет интервальную t-раскраску.
• Если F - набор не менее чем из n ребер, инцидентных одной вершине v полного графа K_{2n + 1}, тогда K_{2n + 1}−F имеет интервальную раскраску.
• Если F - максимальное совпадение полного графа K_{2n + 1} с n≥2, то K_{2n + 1}−F не имеет интервальной раскраски.
• Если п ≤ т ≤ ${ Displaystyle { гидроразрыва {п (п + 1)} {2}}}$, то n-мерный куб Qn имеет интервальную t-раскраску.

Интервальная раскраска ребер двудольных графов

• Для любых m, n ∈ N полный двудольный граф K_{м, н} можно раскрашивать по интервалам, и

(1) w (K_{м, н}) = m + n - gcd (m, n),

(2) Вт (K_{м, н}) = m + n - 1,

(3) если w (K_{м, н}) ≤ t ≤ W (K_{м, н}),тогда K_{м, н} имеет интервальную t-раскраску.

• Если G - двудольный граф, то χ ′ (G) = ∆ (G).
• Если G ∈ N, то G [K_{м, н}] ∈ N для любых m, n ∈ N. Более того, для любых m, n ∈ N имеем

w (G [K_{м, н}]) ≤ (w (G) + 1) (m + n) - 1 и W (G [K_{м, н}]) ≥ (W (G) + 1) (m + n) - 1.

• Если G - связный двудольный граф и G ∈ N, то W (G) ≤ diam (G) (∆ (G) - 1) + 1.

Интервальная раскраска ребер планарных графов^[4]

Интервальная раскраска ребер внешнепланарных графов была исследована Джаро и Кубале и доказала, что все внешние плоские двудольные графы можно раскрашивать по интервалам.^[5]

• Еслиг=г₁например₂ где г₁ и г₂ иметь интервальные раскраски, в которых е имеет внешнюю метку. потом г имеет интервальную раскраску.

Доказательство: Позволять c₁ - интервальная раскраска 'G₁'такой, что е = ху получает наименьшую метку среди ребер, инцидентных Икс и у. Возьмите c₁(е) = 0. Рассмотрим интервальную раскраску интервалов c₁ изг₁ где е получает самую большую метку среди ребер, инцидентных Икс и у.Сказать,c₂(е) = я. Затем строим интервальную раскраску c из г так как с (е ')=c₁(е ') если (е ')∈E (G₁) или же с (е ')=c₂(е ')-я если (е ')∈ НАПРИМЕР₁).

• Если г внешнепланарный граф порядка не ниже 4 без разделяющих треугольников, то он имеет интервальную раскраску.
• Пусть G - граф, полученный удалением некоторых разделяющих ребер при некоторой интервальной раскраске графа ЧАС. потом г раскрашиваемый интервал.
• позволять ЧАС - внешнепланарная триангуляция без отдельных треугольников, и пусть ЧАС=ЧАС₁,-----ЧАС_м быть разложением с соединительными ребрами е₁,----,е_м-1.Если г получается из ЧАС удалив несколько соединяющих ребер, тогда G имеет интервальную раскраску.
• Для любого плоского интервального раскрашиваемого графа г на п вершины т (Г)≤(11/6)п.

Интервальная раскраска ребер бирегулярных двудольных графов с малыми степенями вершин

Двудольный граф называется (a, b) -бирегулярным, если каждая вершина в одной части имеет степень a, а каждая вершина в другой части - степень b. Было высказано предположение, что все такие графы имеют интервальную раскраску. Хансен доказал, что любой двудольный граф G с ∆ (G) ≤ 3 интервально раскрашиваем.

Справедливая раскраска ребер K-интервалов

K-интервальная раскраска ребер графа называется равноправной k-интервальной раскраской ребер, если его множество ребер E разбито на K подмножеств E₁, E₂, ..., E_k такой, что E_я является независимым множеством и условие -1 ≤ E_я ≤ E_j ≤ 1 выполняется для всех 1 ≤i ≤k, 1 ≤j ≤k. Наименьшее целое число k, для которого G является равной раскраской ребра интервала, известно как справедливое хроматическое число раскраски ребра интервала G и обозначается как ${ displaystyle chi _ {eie} (G)}$.

Приложения

Интервальная окраска краев имеет широкое применение в различных областях науки и планирования.

• Одним из основных применений окраски границ интервала является планирование расписания для классов без конфликтов, в этом приложении часы занятий становятся вершинами, и они имеют общую границу, если оба имеют общий временной интервал. Количество цветов, необходимых для окраски краев количество занятий, необходимое для проведения занятий без столкновений. Это используется во всех случаях, когда необходимо организовать два или более мероприятий, избегая столкновений.
• Аналогичное приложение можно найти в планировании времени работы процессоров. планирование передачи файлов в распределенной сети или планирование диагностических тестов в мультикомпьютерной системе, а также планирование задач в системе открытого магазина. Для этой цели разрабатываются различные алгоритмы.
• Окрашивание краев полных графов через интервалы помогает спланировать 2n игр в турнире, чтобы каждая команда играла друг с другом.
• Многие другие приложения возникают при изучении возможности раскрашивания ребер интервалов планарных графов и двудольных графов.

Домыслы

• Для любых m, n∈N, K1, m, n ∈ N тогда и только тогда, когда gcd (m + 1, n + 1) = 1.
• Если г плоский граф на п вершин, то максимальное количество цветов, используемых в интервальной раскраске г не больше (3/2)п.
• Внешнепланарный граф, полученный в результате внешнепланарной триангуляции без разделяющих треугольников путем удаления внутренних ребер, можно раскрашивать по интервалам.

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

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

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