Окраска границ интервала

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

История

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

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

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

Определение

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

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

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

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

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

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

Полный граф интервально раскрашивается тогда и только тогда, когда число его вершин четно.
Если n= _р 2 ^д, где 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 не имеет интервальной раскраски.
Если n ≤ t ≤ ${\frac {n(n+1)}{2}}$ , то n-мерный куб Qn имеет интервальную t-раскраску.

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

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

(1) w ( K _m,n ) = m + n − НОД(m, n),

(2) W ( K _m,n ) = m + n − 1,

(3) если w ( K _m,n ) ⩽ t ⩽ W ( K _m,n ),тогда K _m,n имеет интервальную t-раскраску.

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

w (G[ K _m,n ]) ⩽ (w(G) + 1)(m + n) − 1 и W (G[ K _m,n ]) ≥ (W(G) + 1)(m + n ) − 1.

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

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

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

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

Доказательство: Пусть c ₁ — интервальная раскраска G ₁ такая, что e=xy получает наименьшую метку среди ребер, инцидентных x и y . Возьмем c ₁ (e)=0. Рассмотрим интервальную раскраску c ₁ группы G ₁ , где e получает наибольшую метку среди ребер, инцидентных x и y . Скажем, c ₂ (e)=i . Затем мы строим интервальную раскраску c группы G следующим образом: c(e') = c ₁ (e') , если (e') ∈E(G ₁ ), или c(e') = c ₂ (e') - i, если ( е') ∈ E(G ₁ ) .

Если G — внешнепланарный граф порядка не ниже 4 без разделяющих треугольников, то он имеет интервальную раскраску.
Пусть G — граф, полученный удалением некоторых разделяющих ребер при некоторой интервальной раскраске графа H . Тогда G — интервал, который можно раскрасить.
пусть H — внешнеплоская триангуляция без отдельных треугольников и пусть H = H ₁ ,----- H _m — разложение с соединительными ребрами e ₁ ,----, e _m-1 . Если G получается из H удалением некоторые соединяющиеся ребра, то G имеет интервальную раскраску.
Для любого плоского интервального раскрашиваемого графа G на n вершинах t(G) ≤(11/6) n .

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

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

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

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

Приложения

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

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

Догадки

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

Ссылки

^ Перейти обратно: ^а ^б ^с Асратян А.С.; Камалян Р.Р. (1987), «Интервальные раскраски ребер мультиграфа», в Тоноян Р.Н. (ред.), Прикладная математика. Вып. 5. [ Прикладная математика. № 5 ] (на русском языке), Ереван: Ереван. ун-та, стр. 25–34, 130–131, МР 1003403.
^ Перейти обратно: ^а ^б ^с Петросян, П.А. (2010), «Интервальные раскраски ребер полных графов и $n$ -мерных кубов», Дискретная математика , 310 (10–11): 1580–1587, doi : 10.1016/j.disc.2010.02.001 , MR 2601268
^ Асратян, А.С.; Камалян, Р.Р. (1994), «Исследование интервальных раскрасок ребер графов» , Журнал комбинаторной теории , серия B, 62 (1): 34–43, doi : 10.1006/jctb.1994.1053 , MR 1290629
^ Перейти обратно: ^а ^б Аксенович, Мария А. (2002), «Об интервальных раскрасках плоских графов», Труды тридцать третьей Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 2002) , Конгресс Нумерантиум, том. 159, стр. 77–94, МР 1985168.
^ Джаро, Кшиштоф; Кубале, Марек (2004), «Компактное планирование операций с нулевым временем в многоступенчатых системах», Дискретная прикладная математика , 145 (1): 95–103, doi : 10.1016/j.dam.2003.09.010 , MR 2108435

См. также

[ak87-1] Перейти обратно: ^а ^б ^с Асратян А.С.; Камалян Р.Р. (1987), «Интервальные раскраски ребер мультиграфа», в Тоноян Р.Н. (ред.), Прикладная математика. Вып. 5. [ Прикладная математика. № 5 ] (на русском языке), Ереван: Ереван. ун-та, стр. 25–34, 130–131, МР 1003403.

[p10-2] Перейти обратно: ^а ^б ^с Петросян, П.А. (2010), «Интервальные раскраски ребер полных графов и $n$ -мерных кубов», Дискретная математика , 310 (10–11): 1580–1587, doi : 10.1016/j.disc.2010.02.001 , MR 2601268

[ak94-3] Асратян, А.С.; Камалян, Р.Р. (1994), «Исследование интервальных раскрасок ребер графов» , Журнал комбинаторной теории , серия B, 62 (1): 34–43, doi : 10.1006/jctb.1994.1053 , MR 1290629

[a02-4] Перейти обратно: ^а ^б Аксенович, Мария А. (2002), «Об интервальных раскрасках плоских графов», Труды тридцать третьей Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 2002) , Конгресс Нумерантиум, том. 159, стр. 77–94, МР 1985168.

[gk04-5] Джаро, Кшиштоф; Кубале, Марек (2004), «Компактное планирование операций с нулевым временем в многоступенчатых системах», Дискретная прикладная математика , 145 (1): 95–103, doi : 10.1016/j.dam.2003.09.010 , MR 2108435

[1]

[2]

[3]

[4]

[5]