Об интервальных реберных раскрасках мультиграфов

П.А. Петросян

Ереванский Государственный Университет, Институт проблем информатики и автоматизации НАН РА

Интервальной 1 -раскраской мультиграфа О назовем раскраску ребер О в цвета 1,2,… Д, при которой в каждый цвет і, 1 < і < 1;, окрашено хотя бы одно ребро мультиграфа О, и ребра, инцидентные каждой вершине, окрашены в последовательные цвета. Доказано, что если 2 — связный мультиграф О имеет интервальную 1 — раскрасподпись: (д(о) - 1), где у(о)- множество вершинподпись: ку, то 1 < 1+‘ |у(о)Т 2

О,        а А(О) максимальная из степеней вершин О . Показано, что полученная оценка неулучшаема.

Доказана справедливость гипотезы М. Аксенович для 2-связных планарных мультиграфов О с А(О) < 4.

Доказано, что если кубический мультиграф (граф) О имеет интервальную 1-раскраску, то Ї < |У(О) +1 (1 < |У(О)|), причем во

множестве кубических графов интервальная |У(О)|раскраска существует только для К4.

Показано, что любой двудольный мультиграф О с А (О ) = 3 имеет интервальную 3или 4раскраску.

Ключевые слова: мультиграф, кубический граф, реберная раскраска, интервальная раскраска

Обозначения, определения, цель работы

Пусть О неориентированный мультиграф, V(G) множество вершин мультиграфа О, Е(О) множество ребер мультиграфа О . Для двух различных вершин и и V мультиграфа О через Б(иу) обозначим множество ребер мультиграфа, инцидентных вершинам и и V, а через р(иу) мощность множества E(uv) . Степень вершины V в О обозначим через ёо(у), максимальную из

степеней вершин через л (О). а хроматический класс О через х (О). Не

определяемые понятия и обозначения можно найти в [6].

Интервальной 1 -раскраской мультиграфа О назовем раскраску ребер О в цвета 1,2,… Д, при которой в каждый цвет 1, 1 < 1 < 1, окрашено хотя бы одно ребро мультиграфа О, и ребра, инцидентные каждой вершине V е У(О) , окрашены в ёо^) последовательных цветов. Мультиграф О назовем интервально окрашиваемым, если существует 1 > 1, для которого О имеет интервальную 1 раскраску. Множество всех интервально окрашиваемых мультиграфов обозначим через N. Для О е N обозначим через ш(О) и W (О), соответственно,

наименьшее и наибольшее 1 , для которого О имеет интервальную 1 раскраску.

Определение интервальной реберной раскраски мультиграфа было введено в [1]. В работе [1] А.С. Асратяном и Р.Р. Камаляном были получены следующие результаты:

Теорема 1. Если О е N, то х ‘( О ) = А ( О).

Теорема 2. Пусть О регулярный мультиграф. Тогда:

О е N тогда и только тогда, когда х'( О) = А (О);

если О е N и А (О) < г < W (О), то мультиграф О имеет интервальную 1 — раскраску.

Некоторые результаты по интервальным реберным раскраскам мультиграфов были установлены в [3].

Целью настоящей работы является исследование параметров ш(О) и

W (О) для интервально окрашиваемого мультиграфа О .

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

подпись: доказательство. рассмотрим интервальную w(g) - раскраску а мультиграфа о. пусть а(е) = 1, а(е') = w(g), где е = uv, а е' = и'у'. так как мультиграф о является 2 - связным, то существует простой цикл с , содержащий реб-Теорема 3. Если О 2 — связный мультиграф и О е N , то

Об интервальных реберных раскрасках мультиграфов

подпись: 14ра e и е. Теперь рассмотрим простой цикл C. Пронумеруем вершины цикла C в направлении от u к u’ и от v к V: u = u1,u2,^,us.1,us = u’ и

,           • f 1 Г1 V(G)|

v = Vi, V2,• • • ,vt-i,vt = v, где s,t > 1. Легко видеть, что min {s,t} < J

подпись: |v(g)|
2
подпись: . ясно, что в этом случаеПредположим для определенности, что s <

а (uiu2 )< dG (ui),

подпись: а(u2u3 ) < а (u1u2 ) + dG (u2 ) — 1,

а (uiui+1) < а (ui-1ui) + dG (ui)-1,

а (us-1us ) < а (us-2us-1) + dG (us-1)-1

W(G) = а (e’) = а ( UV ) < а (us-1us ) + dG ( us )1. Следовательно,

|V(G)|

подпись: (д (g) - 1).W(G) < 1+Х( (ui)-1)< 1+

i=1

Теорема 3 доказана.

Следствие 1. Если G 2 — связный мультиграф с A(G) = 4, и G е N , то

подпись: w(g) < 3подпись: + 1.|V(G)|

2

Из данного следствия вытекает справедливость гипотезы Аксенович [2] для интервально окрашиваемых 2 — связных планарных мультиграфов с максимальной степенью не более 4.

Заметим, что если О связный кубический мультиграф и О е N, то, по теореме 1, х'(О) = 3 и, следовательно, О 2-связный мультиграф.

Следствие 2. Если О связный кубический мультиграф и О е N, то

W(G) < |У(О)|+1.

Теперь покажем, что верхняя оценка теоремы 3 достижима. Имеет место следующая

Теорема 4. Для любых п,г > 2 существует 2-связный мультиграф О с |У(О)= 2п и Л (О) = г такой, что О е N и W(G) = п (г — 1)+1.

Доказательство. Ясно, что для доказательства теоремы достаточно построить мультиграф О, удовлетворяющий условию теоремы.

Определим мультиграф Оп г следующим образом:

У(°п,г ) = {и1,и2,_,ип,У1,у2,_ ,Уп} и Е (Оп,г ) = {и1У1, ипУп 1 Ц (и1У1 ) = Ц (ипУп ) = г 1} и {иіиі+1 ,УіУі+11 1 < і < п 1 и

и {иіУі| ц(иіуі )= г 2, 2 < і < п — 1}, п,г > 2.

Ясно, что Оп г 2 -связный мультиграф с | V (Опг)| = 2п и А ^Опг) = г.

Покажем, что мультиграф Опг имеет интервальную (п (г — 1) + 1) — раскраску. Для этого определим раскраску а ребер мультиграфа Оп г следующим образом: окрасим сначала ребра из множества Е(ихУх) в цвета 1,2,…,г-1, а ребра из множества Е (ипУп ) в цвета (п — 1)( г — 1) +2,…,п (г — 1) +1. Затем окрасим ребра из множества      Е (и;у;)            в цвета

(і 1)(г 1)+2,…,і (г — 1), 2 < і < п — 1, а ребра ^и^ и у^^ окрасим в цвет Дг — 1)+1, 1 < j < п — 1. Нетрудно проверить, что а является интервальной (п (г — 1) + 1) -раскраской мультиграфа Оп г.

Теорема 4 доказана.

Теперь покажем, что если Освязный кубический граф и О є N, то Ш(О) < |У(О)|.

Теорема 5. Пусть Освязный кубический граф и О є N. Тогда W(G) < |У(О)|. Кроме того, если О ^ К4, то W(О) < |У(О)| — 1.

Доказательство. Прежде всего, заметим, что из следствия 2 вытекает, что W(О) < |У(О)| + 1 для интервально окрашиваемого связного кубического графа О.

Покажем, что W(G) < |У(О)|.

Пусть а является интервальной (| У(О)|+1) — раскраской кубического графа О. Пусть, далее, а(е) = 1, а(е’) = |У(О)|+1, где е = иу, а е’= и’у’. Так как

О связный кубический граф и О є N, то О является 2 — связным и, следовательно, существует простой цикл С, содержащий ребра е и е’. Рассмотрим простой цикл С. Пронумеруем вершины цикла С в направлении от и к и’ и от

Об интервальных реберных раскрасках мультиграфов

подпись: 16V к V’: и = и1,и2,^ ,и8-1,и8 = и’ и V = УЬУ2,…, У1-1, = V’, где 8,1 > 1. Лег,=|У(О>|.

ко видеть, что в этом случае Б = 1 = -—2—. Ясно, что

а (и1и2 ) = а ( V1V2 ) = 3, а ( и2и3 ) = а ( ^3 ) = 5,

подпись: а(и1и1+1 ) = а (V1V1+1 ) = 21 + 1,

а (и8-1и8 ) = а (Vt-1Vt ) = 28 1 = 21 1,

W(О) = а (е’) = а (и V) = 2б + 1 = 21 +1.

•           |У(О)|  . ч .

Отсюда следует, что для 1 = 1,2,…^—— UlVl еЕ(О) и а(и^) = 21,

что приводит к противоречию 1 = а (uv) = а(е) = а (и^1) = 2.

Ясно, что К4 е N и W(K4) = |У(К4)| = 4. Теперь покажем, что если О связный кубический граф, О ^ К4, и О е N, то W(G) < |У(О)| — 1.

Пусть теперь |У(О)| > 6 и в является интервальной |У(О)|-раскраской кубического графа О. Пусть, далее, Р(е) = 1, Р(е’) = |У(О)|, где е = uv, а

е’= иV’. Так как Освязный кубический граф и О е N, то О является 2связным и, следовательно, существует простой цикл С , содержащий ребра е и е’. Рассмотрим простой цикл С. Пронумеруем вершины цикла С в направлении от и к и’ и от V к V’: и = и1,и2,. ,и3-1,и8 = и’ и V = Vl,V2,…       = V’, где БД > 1. Легко видеть, что в этом случае

|У(О)|

Б = 1 =—2—. Рассмотрим два случая.

Случай 1. Р (и1и2 )= Р (V1V2 ).

Если Р(и1и2 ) = Р(V1V2 ) = 2 то Р(и^2 ) = Р(V1U2 )= 3 и Р (и2и3 ) = Р ( V2V3 ) = 4 Р (и3и4 ) = Р ( ^4 ) = 6,

в (и1и1+1 ) = Р ( У1У1+1 ) = 2i,

Р (us-1us ) = Р ( У1-1У1 ) = ^ — 2 = 2 — 2,

W(G) = в (е’) = в (иУ) = 2s = 21.

• К(О)| о( ■

Отсюда следует, что для 1 = 3,…, — 1—— и^ е Е(О) и в(и^) = 21 — 1,

что приводит к противоречию |У(О)| = в (иУ) = в(е’) = в (UsVt) = |У(О)| — 1.

Аналогично рассматривается случай в ( и^2 ) = в (У1У2 ) = 3.

Случай 2. в (и1и 2 ) в ( У1У2 ).

Если в (и^ ) = 2 и в ( у^2 ) = 3, то

в ( и2и3 ) = 4 в ( и3и4 ) = 6,

в ( и1и1+1 ) = 21,

в (Us-1Us ) = 2s — 2 = 21 — 2, |У(О)| = в (е’) = в (и’У) = 2s = 21.

Отсюда следует, что существует ребро и^, е Е(О), где 3 < , < 1, в (у, ) = 3. Теперь рассмотрим простую цепь

Р = (у,у1и„и„и1у,0,^0,у,0у,0 „,у,0 „,.,у1,у1и„и, ).

Я Р |У(О)| 1

Ясно, что длина цепи Р меньше, чем -——— 1, откуда следует, что

( 1у(О)1 ^

|У(О) = в(иУ) = в(е’) = в(и,У1 )<2 — 1 +1 = |у(О)| — 1,

V 2 )

что является противоречием.

Аналогично рассматривается случай в (и^ ) = 3 и в ( ) = 2. Теорема 5 доказана.

Об интервальных реберных раскрасках мультиграфов

подпись: 18Теорема 6. Для любого п > 3 существует связный кубический граф О с |У(О)|= 2п такой, что О є N и W(G) = |У(О)| — 1.

Доказательство. Ясно, что для доказательства теоремы достаточно построить кубический граф О , удовлетворяющий условию теоремы. Определим граф Оп . Положим О3 = К3 3. Пусть, теперь п > 4. Определим граф Оп следующим образом:

У(Оп ) = {и1,и2,.,ип,у1,у2,.,уп } и Е (Оп ) = {и1у1,и1у2 , у1и2 ,ип-1уп ,ипуп-1 ,ипуп } и {иіиі+1 ,уіуі+11 1 ^ і < п 1} и

и{иіуі| 3 < і < п — 2}.

Ясно, что Оп связный кубический граф с |У (Оп )| = 2п.

Покажем, что Оп имеет интервальную (2п — 1) — раскраску. Прежде всего заметим, что К33 є N и W(Kзз) = 5, откуда следует, что граф О3 имеет интервальную 5 — раскраску. Пусть, теперь п > 4. Определим раскраску а ребер графа Оп следующим образом: окрасим сначала ребро и1у1 в цвет 1, ребра и1у2,у1и2 в цвет 3, ребра ип-1уп,ипуп-1 в цвет 2п 3, а ребро ипуп в цвет 2п — 1. Затем окрасим ребро иіуі в цвет 2і — 1, 3 < і < п 2, а ребра ^и^ и УjУj+1 окрасим в цвет 2j, 1 < j < п — 1. Нетрудно проверить, что а является интервальной ( 2п — 1) -раскраской графа Оп.

Теорема 6 доказана.

Из теорем 2 и 6 вытекает следующее:

Следствие 3. Для любого п > 3 существует связный кубический граф О с |У(О)|= 2п такой, что

О є N

ш (О) = 3,

W (О ) = 2п — 1,

если ш ( о ) < 1 < W(о), то О имеет интервальную 1 — раскраску. Отметим, однако, что существуют кубические графы О є N, у которых

|У(О)|

з„аче„„е Параметра   блшко к —. Так, например, в работе [5] 6ь,ло

показано, что для «лестниц Мебиуса» М^п (п > 2) с 2п вершинами справедлива следующая

Теорема 7. При п > 2

м2п е N

ш(М2п )= 3

W (М2п ) = п + 2,

Если ш(М2п )< 1 < W(М2п ), то М2п имеет интервальную 1раскраску.

В заключение рассмотрим двудольные мультиграфы. В работе [4] была доказана следующая

Теорема 8. Если О двудольный граф с А(О) < 3, то О е N и ш(О) < 4.

Покажем, что теорема 8 справедлива также для произвольного двудольного мультиграфа О с А(О) < 3.

Теорема 9. Если О двудольный мультиграф с А(О) < 3, то О е N и ш(О) < 4.

Доказательство. Прежде всего заметим, что если А(О) < 2, то О е N и ш(О) < 2.

Теперь предположим, что А(О) =3. Индукцией по |е (О) покажем, что двудольный мультиграф О имеет интервальную 3 или 4 — раскраску.

При |е (О)| < 4 доказываемое очевидно. Пусть теперь |е (О)| > 5, и утверждение верно для всех мультиграфов О’ с |е (О’)| < |е (О)|. Докажем, что утверждение верно для мультиграфа О. Если О не имеет кратных ребер, то утверждение вытекает из теоремы 8. Пусть теперь uv е Е(О) и р (V) > 2. Рассмотрим четыре случая.

Случай 1. р (V) = |{е1,е2,е3} = 3.

Положим, О’ = О — E(uv). Из индуктивного предположения вытекает, что существует интервальная 3 или 4 — раскраска а мультиграфа О. Теперь окрасим ребро е1 в цвет 1, 1 = 1,2,3. Легко видеть, что полученная раскраска является интервальной 3 или 4 -раскраской мультиграфа О.

Случай 2. р (V) = |{еь е2 }| = (и) = (v) = 2.

Положим, О’ = О — E(uv). Из индуктивного предположения вытекает, что существует интервальная 3 или 4 — раскраска а мультиграфа О. Теперь окрасим ребро е1 в цвет 1, 1 = 1,2. Легко видеть, что полученная раскраска является интервальной 3 или 4 — раскраской мультиграфа О.

Случай 3. р (V) = |{еь е2 }| = dG(v) = 2 и ёО (и) = А(О) = 3.

Об интервальных реберных раскрасках мультиграфов

подпись: 20Ясно, что в этом случае в мультиграфе G существует мост uw є E(G). Положим, G’ = G — E(uv). Из индуктивного предположения вытекает, что существует интервальная 3 или 4 — раскраска а мультиграфа G.

Случай 3.1. а (uw) < 2.

Окрасим ребро e в цвет а (uw) + i, i = 1,2. Легко видеть, что полученная раскраска является интервальной 3 или 4 — раскраской мультиграфа G.

Случай 3.2. а (uw) > 3.

Окрасим ребро Єі в цвет а (uw) — i, i = 1,2. Легко видеть, что полученная раскраска является интервальной 3 или 4 — раскраской мультиграфа G.

Случай 4. ц (uv) = |{ei,e2 }| = 2 и dG (u) = dG (v) = A(G) = 3.

Ясно, что в этом случае в мультиграфе G существуют вершины x,y є V(G) (x * y) такие, что ux є E(G) и vy є E(G). Положим

G’ = (G — E(uv) — ux — vy) + xy. Из индуктивного предположения вытекает, что существует интервальная 3 или 4 — раскраска а мультиграфа G.

Случай 4.1. а (xy )< 2.

Удалим ребро xy из G’ и окрасим ребра ux и vy в цвет а (xy), а ребро Єі окрасим в цвет а (xy) + i, i = 1,2. Легко видеть, что полученная раскраска является интервальной 3 или 4 — раскраской мультиграфа G.

Случай 4.2. а (xy )> 3.

Удалим ребро xy из G’ и окрасим ребра ux и vy в цвет а (xy), а ребро Єі окрасим в цвет а (xy) — i, i = 1,2. Легко видеть, что полученная раскраска

является интервальной 3 или 4 — раскраской мультиграфа G.

Теорема 9 доказана.

Автор благодарен О. Тананяну и В. Мкртчяну за полезные советы при выполнении работы.

ЛИТЕРАТУРА

Асратян А.С., Камалян Р.Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. Ер., Изд-во ЕГУ, 1987. Вып. 5. СС. 25-34.

Axenovich M.A. On interval colorings of planar graphs // Congr. Numer. 159, 2002. PP. 77-94.

Камалян Р.Р. Интервальные реберные раскраски графов // Диссертация на соискание ученой степени кандидата физ.-мат. наук, ИМ СО АН СССР. Новосибирск, 1990, 103 с.

Hansen H.M. Scheduling with minimum waiting periods // Master’s Thesis, Odense University, Odense, Denmark, 1992.

Petrosyan P.A. Interval edge colorings of Mobius ladders // Proceedings of the CSIT Conference. Yerevan, 2005, pp. 146-149.

West D.B. Introduction to Graph Theory Prentice-Hall, New Jersey, 2001.

ON INTERVAL EDGE-COLORINGS OF MULTIGRAPHS

P.A. Petrosyan

подпись: ((g) - l),where v(g) is the set of vertices of gподпись: coloring, then t < 1+An edge-coloring of a multigraph G with colors 1,2,…,t is called an interval t — coloring if for each i, 1 < i < t, there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It’s proved that if a 2-connected multigraph G admits an interval t |V(G)|

2

and A(G) is the maximum degree of a vertex of G. It’s shown that this upper bound is sharp. This result implies that Axenovich’s conjecture on 2-connected planar multigraphs G with A(G) < 4 is true. For some classes of cubic and subcubic multigraphs and graphs having an interval t-coloring upper bounds for t are obtained.

Вестник РАУ. № 1, 2011, 33-46

Материал взят из журнала Вестник выпуск Физико-математические и естественные науки