Интервальная раскраска края

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

Концепция последовательной раскраски рёбер была введена с терминологией « интервальная раскраска рёбер» Асратяном и Камалианом в 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).

• Полный граф является интервально раскрашиваемым тогда и только тогда, когда число его вершин четно.
• Если n= _p 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 не имеет интервальной раскраски.
• Если n ≤ t ≤${\displaystyle {\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 ( К _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.

Интервальная раскраска ребер внешнепланарных графов была исследована Джиаро и Кубале и доказала, что все внешние планарные двудольные графы допускают интервальную раскраску. ^[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') ∈ 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-интервальной раскраской ребер, если ее множество ребер E разбито на K подмножеств E ₁ ,E ₂ ,...,E _k таким образом, что E _i является независимым множеством и условие -1 ≤ E _i ≤ 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.
• Если G — планарный граф на n вершинах, то максимальное количество цветов, используемых при интервальной раскраске G, не превышает (3/2) n .
• Внешнепланарный граф, полученный из внешнепланарной триангуляции без разделяющих треугольников путем удаления внутренних ребер, является интервально раскрашиваемым.

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