Исследование свойств реберных раскрасок графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

I? Л" I *

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи МУЗЫЧУК Илья Анатольевич

УДК 519.1

ИССЛЕДОВАНИЕ СВОЙСТВ РЕБЕРНЫХ РАСКРАСОК ГРАФОВ

01.01.09 — математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва —1991

Работа выполнена на кафедро математической кибернетики Московского государственного университета им. М.В. Ломоносова

НАУЧНЫЙ РУКОВОДИТЕЛЬ - кандидат физико-математических наук,

доцент Гарий Петрович Гаврилов

ОФЩШЫШЕ ОППОПЕШЫ - доктор физико-математических наук,

ВЕДУЩАЯ ОРГАНИЗАЦИЯ - Государственный университет республики

Д053.05.38 в Московском государственной университете ил. М.В. Ломоносова по адресу: 115699 Москва, ГСП, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й гум. корпус, факультет ВМиК, ауд. 685.

С диссертацией можно ознакомиться в научной библиотеке факультета ВМиК.

Автореферат разослан "_"_195_г.

профессор

Владимир Константинович Леонтьев; кандидат физико-математических наук Сергей Владимирович'Юшмадав

Беларусь, кафедра уравнений математической физики механико-математического факультета, г. Минск

в

Учёный секретарь Специализированного Совета профессор

Н.П. Трифонов

«tV/ШСШШ S>E. ГГЙ1

«а. t.. иг»

тдьд диссертаций

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТУ

АКТУАЛЬНОСТЬ ТЕШ. Одним из важных объектов исследований в теории градов являются рэбэрныа раскраски и их свойства. В 1964 г. Визинг* показал, что хроматический индекс ^С'( О ) цультиграфа С с максимальной степенью верши; Д ( С ) и максимальной кратностью рёбер у*- ( О ) удовлетворяет следующим оценкам:

А (С ) ¿Х^К Л10+/(С).

Для простых графов ( о С ) = I ) это позволило поставить следующую проблему классификации: определить, катаю графи принадлежат массу 1( %(&) = Д(&)),а какие - классу 2 ( %'{&)-= Д ( Сг) +1 ). Необходимого и достаточного условия принадлежности графа одному из этих двух классов пока не найдено. Получен лишь ряд частных признаков ( см. например2,3 ).

В исследованиях, связанных с проблемой клас^ифпкахщд, существенную роль играет понятно графа, критического но рёберной раскраске. Граф назяваотся критическим по рёберной раскраске, если он связен, принадлежит классу 2 и удаление любого его ребра понижает хроматический индекс.

Тот факт, что все найденные до 1978 г. конструкции и метода приводили к построению критических графов только с нечётным числом вершин, дал основании Якобсену^ предположить, что такови все крити-

* Визинг В.Г. Об оценке хроматического масса р -графа // Дискр.

анализ. - 1964. - Bun. 3. - С. 25 - 30. 2 Fiorini 5., WitsonRJ. Edge-colorings of graphs -Res. Motes in Math., V.(6.~ London: Pitman, 1977.

ri

Зыков А.Л. Основы теории графов. - М.: Наука, 1987. - 384 с.

4 Jakobsen l.T. On critical graphs with chromatic indeK 4 // Be sere te Math. -1974. -tl9. -P. 265-276.

ческие гргфн. Байнеке и Фкорини* доказали справедливость гипотезы ^ Якобсона при / V ( О )1 10 и для 3-критическюс (с Д ( £ ) = 3 ')" " градов с 12 вершинами. Однако в полом гипотеза оказалась неверна, -первый контрпример к ней был построен Гольдбергом2 в 1978 г. Тем до менее остался невыясненным вопрос о существовании многочисленных семейств критических градов с чётным 'телом вершия { V ( & )1 > 12.

С связи с этим возникла потребность:

а) в развитии известных ( как предложенный в1 ) и создании новых методов исследования графов на критичность по рёберной раскраске ;

б) в поиске специальных классов гра|юв, на которых данные методы работают особенно эффективно;

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

ЦМЬ РАБОТЦ. Разработка методов исследования грпфов на критичность по рёберной раскраске и оценка их сложности; изучение структурных, метрических свойств критических градов, а тагло свойств, связанных с симметрией этих грогров и наличием в них максимальных паросочетялкД згдашоК мощности; исследование свойств реберных расктсок граГюв, подозрительных на критичность; опокхн чрсяй критических подх'рп^оп в произвольном графа класс 2; доказательство несуществования некоторых семейств критических градов с 12 вершинами; создание алгоритма, позволяющего ропать задачу ктпссяЪпг./иш для графов с А ( & ) = 3 и исследовать их на 3-критпчкость; оценка объективности этого алгоритма.

НАУЧНАЯ НОВИЗНА.

(а) Развит подход, использованный в1 при обосновании гипотезы Якобссна для графов с| V С & )| й 10 и с/ V ( О )| = 12, Л ( & ) =3. Предложено два новых подхода к исследованию графов на критичность по рёберной раскраске, которые, наряду с предыдущим подходом, дают

1 Beineke L.W., Fiorini S. Onsmait graphs critical with respect to edqe-coZourinys // Discrete Mathr!976rHS6. -p l09-'2f

Гольдборг M.K. Критические графы с чётным числом вершин // Сооб. АН ГССР. - 1979. - Т. 94. - ii I. - С. 25 - 26.

возможность:

1) выявлять некритичность исследуемого графа;

2) устанавливать принадлежность некритического гра$а классу I;

3) доказывать несуществование семейств критических графов, имеющих один и тог же стеленной список.

(б) С помощью трёх вышеуказанных подходов установлено, что

но существует 4-кратических (с А ( & ) = 4 ) 12-вершинних гра]>ов. Кроме того, доказало несуществование некоторих 5-критических ( с Д( G ) = 5 ) графов с 12 вершинами.

(в) Даны оценки сложности предлагаемых подходов. Получена связанная со сложностью одного из них нижняя оценка числа критических подграфов в графе класса 2.

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

(д) Предаол!ен алгоритм, решающий задачу классификации дош графов с Д( G ) = 3 с параллельной проверкой на 3-критичность, и дана оценка его эффективности.

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Диссертация носит теоретический характер. Ее результаты могут найти применение в теории графов, комбинаторном анализе, проблемном программировании. Из практических применений можно указать задачу составления расписаний.

АПРОБАЦИЯ РАБОТУ. Результаты диссертации докладывались и об-суэдались на Второй Меядународной Конференции по дискретной математике и её применениям ( ЕлагЬевград, 1990 ); на семинаре по математическим вопросам кибернетики под руководством чл.-корр. АН СССР, проф. C.B. Яблонского ( МГУ, 1990 ); на семинаре по комбинаторной математике под руководством профессора К.А. Рыбникова ( ИГУ, 1991 ).

ПУБЛИКАЦИИ. Основные результаты диссертации опубликованы в пяти печатных работах [i] - [5J.

СТРУКТУРА И ОБЪЁМ РАБОТЫ. Диссертация выполнена на 109 страницах машинописного текста, состоит из введения, ipëx глав и списка литературы ( 67 названий ).

КРАТКОЕ СОДЕРНШЕ РАБОТЫ

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

ГЛАВА I. Описываются три метода исследования графов на критичность по рёберной раскраске: структурно-метрический подход, метод удаления I-факторов, развивающий подход, предложенный Байнеке И Фиорили в*, и метод удаления цветных классов. Рассматриваются три важных класса графов, удобных с точки зрения применения этих методов.

В § I.I излагается структурно-метрический подход к исследованию графэв на критичность. Формулируются необходимые признаки критичности граЪа, выявленные Визингом и Фиорини ( см.2 ). Будем называть критические грары с максимальной степенью вершин û Сд -грарами. Тогда указанные признаки мокно сформулировать в ввде следующих пяти утворадений:

Утг.огждснио I.I. Критически" граф не содержит точек сочленения.

Утверждение 1.2. Пусть U и О" - смежные вершлны Сд -графа G • Тогда сумма их степеней удовлетворяет неравенству

de.gG (u) +de(j& ((*)> д +

„х-

Утаорздение 1.3. Пусть U и О* - смоглшэ вершины Сд -графа G и пусть deg& (U) =/< . Тогда вершина О смогла не менее чем с А-к + I ве раииами степени Д , отличными от U

Утверждение 1.4. Пусть G - GA -граф с п вершинами, m ребрами и минимальной степенью б . Тогда

i («- I) Д/2 + I, если П - 2к + I; m 4 <

(п- 2) Д/2 I, если П=2к.

1 Ôeîneke L.W., FtoriniS. On small graphs critical with respect to edge-colourings ff Discr. Math.-f976.-M6.-p. tQS-tti

2 Fiorini 5-, Wilson R.J. Edge-colorings of 9™PhJ-Res. Not. in Math. - VJ6.~ London: ßltman, тт.

Утверждение 1,5, Пусть G - Сл -граф и пусть Л\j { 2 é, j it Ь. ) означает число вершин степени j в G . Тогда

zYL ч/ц-ik

j-2

Определим расстояшэ J3q ( Ц, О) между вершинами U и № в графе G- как число рёбер Ь кратчайшей цепи, юс соединяющей. Само название структурно-метрического подхода говорит о том, что он связан с оценками расстояний между вершинами заданных степеней. Действительно, утверждения 1.2 и 1.3 тлеют следствия метрического характера:

Следствие 1.6, Пусть О - Сд -граф и пусть степени двух его вершин Uni?" удовлетворяют неравенству

c/egG (и) + deg& Со-}^ д ♦ i.

Тогда j>ç(U,&)> 2. ^

Оледствиэ 1.7. Пусть U и О - вершины Сд -графа G и пусть deg &. (а) = 2, ctef^ (tfOé Д- I. Тогда fia 3.

Обозначим через 77д. совокупность всех графов, обладающих необходимыми признаками -критичности ( утверждения I.I -1.5 ). Тогда суть структурно-метрического подхода можно определить следующим образом: выяснить, принадлежит ли исследуемый граф с максимальной степенью Д. классу 77д , н если нет, то отбросить его как заведомо не критический. Необходимая для этого проверка имеет полиномиальную сложность. ^

В § 1.2 рассматривается класс Сд -графов с минимальной степенью 2 - Сд 2 • Доказывается, что для графов из этого класса тлеет место более сильная метрическая оценка, нежели установленная в следствии 1.7: ' ^

Теорема 1.8. Пусть IX и № - вершины Сд -графа G пусть deg й CU) =2, Д- 2.

Тогда (U,U") ^ 4.

Доказательство этой опенки основывается на методе перекрасок максимальных двухцветных цепей.

Таким образом, класс Грефов из Tîcx с минимальной

степенью 2 допускает такое сужение до подкласса 77д*г графов, удовлетворяющих заключению теоремы 1.8, что графы, принадлежащие

\ /ГД)2 , но является критическими. Кроме того, теорема 1.8 имеег следствием результат, усиливающий оцешдг числа вершин степени Д , данную в утверждении 1.5, дая графов иг класса Сл,г "Р11 А>4и Пд_/ = 0: Теорема 1.9. Пусть граф G 6 СЛ 2 , Д > 4. Тогда

Д- 2

Нд > 3 4 П2(Л" [ + 2 /(j - I).

* J = 3

В § 1.3 рассматривается класс СЛ -графов с однозначно определяемым цветным покрытием. Правильная раскраска рёбер Сд -rpaja G в Л t I гостов называется напряжённой, если в один из цветов в этой раскраске ( 0-й цвет ) раскрашивается только одно ребро. Если это ребро - (U,U")t то соответствующая напряжённая раскраска V обозначается через Ч'и^ ' Множества цветов, присутствующих и отсутствующих в вершине НУ при этой раскраске, обозначаются соответственно через Q (Ш) = dip (It*-) и Q (0У-) = q ^ (us}. Множество всех наиряжошнос раскрасок С* -графа & будем обозначать через ф ( G).

Опподплонцо, Будем говорить, что Сд -грат]) G- имеет однозначно определяемое иветное локрытие ( ООЦ-покрктие ) ранга Г , Г > 0, cam

min I Г\ (Я Í = г .

y>e0(G) ireV(G-)

В следующей теореме устанавливается необходимый и достагочннй критерий наличия ООЦ-покрнтил ранга г у Са -графа.

Теорема I.IO. Сд-граф G- с п вершина».« и т робра-ш имеет ООЦ-ткщтпе ранга г , г > О, тогда и только тогда, когда П = 2 k ( KüíN), 0<г4 А - з и m = (к- 1)д + i + г.

До1сазнвается метрические и другие свойства Сл -графов с ООЦ-покрытием ранга Г : * •

Теорема 1.11. Пусть G - Сл -граф, имеющий ООЦ-покрыгие ранга Г , и пусть степени двух его вершин U. и 1У удовлетворят' неравенству

degG {U) +degG (W4 A + r + i,

где О А- 3.

Тогда 2. ^

Теорема I.I2, Пусть (г - Сд -граф с минимально!! степенью <5" , !У,гею:!(!1Й ООЦ-дакрнтмо ранга г , где 0 Г4 Д - 3. Тогда +2.

Теорема 1,13. Пусть & - Сд -граф с Л = 2 к вершинами и т рёбрами, где т = (к - 1)А + I + Г ( О < ГЧ Д - 3 ). Тогда & имеет по крайней море Г непересекающихся I-факторов.

В § 1.4 рассматривается класс Сл -графов с веерной симметрией. Пусть ¥> - правильная рёберная раскраска графа G . Веером и вершине О графа Gr с начальным ребром ( 0-,U9ji) будем называть последовательность рёбер {( О", Щ), (I?*, ,..., (í>-, Lüj)

такую, что: I) (t?", Ц {W() для ¿ = 1,2.....S- I; 2) при

добавлении к этой последовательности любого не принадлежащего ей ребра (l^.U^) С если такое найдётся ) нарушается свойство I) для

последовательности {((?", ^i)..... ( ( ^.^t) = (V,

..., (Í^.U^s ) - (V-fUr/tj) , где Ié. Веер в вершине V с началъни:д ребром ((?-,UJf), раскрашенным в цвет , будем обозначать через F/iy. (U^, С/ ).

Определение. Пусть U. и О - смежные вершины С* -графа G- . Назовём окрестность вератин if- веерно-ешметрпчной относительно вершины U , если для любой вершины Uf Фи. из этой окрестности существует напряжённая раскраска Y'u, о- графа & » при которой ребро (t?,Li>) приладлекит вееру в всриине О , начинающемуся с ребра, раскраденного в цвет С € ^ )• Будем говорить, что С'*-~рэф G обладает веерной симметрией р -го порядка, где 0 ¿p¿¡ А - 2, если для любой пары смехяшх вершш U. и Ц^ , суша степеней которых de^g. (U.) + deg¿ А + р + 2,

окрестность вершины & веерно-симметрична относительно верптны U •

Доклз'.шастся следующая леша^

Домма 1.14. Пусть б- - С л -граф с фиксированной напряжённо« раскраской у0 = » deg q W> ak » deg^ (И = ■= Д- k + 3 + P , 1Д0 2 4 Л , oé P4 к - 2, и пусть

Fn^t tes, С, ) = (»-.ug)..........-

веер такой, ■'tro Cj£tJ (U). Тогда:

1) s 6 p i-1;

2) deg д -p+i -l, i»

С помощью леммы I.I4 устанавливается теорема, которая представляет некоторое обобщенно утверждения 1.3 для С* -графов, обладающих веерной симметрией ненулевого порядка:

Теорема I.I5. Пусть & - С* -ГР35» обладдаций воерной симметрией' р -го порядка, где 04 р£ Д - 2, и пусть и и Í*- - , пара сматних вершин в & со стспеняма deg g, CU) => к и

deg <U ) « Д-к. + 2 +р', 1ДЭ 24к4 Д , 04pktnlnfp ,К- 2}

Тогда любая вершина US- U из окрестности вершины I?- либо имеет степень Д , либо deg g, (U*-)^ Д-р'.

^Kaic следствие из теоремы I.I5, выводится метрическое свойство Сд-графов, обладающих веерной симметрией р-го порядка: Теорема I.I6. Пусть G - Сд -граф, обладающий веерной симметрией р -го порядка, где 06 pé Л - 2, и пусть U. и О -вершины в G со степенями deg g. (U) =k4 р +2 zdeQç, 4Д -К + I.

Тогда />g(U,0)>3. ,

Следующие два параграфа посвящены изложению двух методов исследования графе , из класса 7Гд на критичность, которые позволяют находить точное значение хроматического индекса графа в том случае, когда он не является критическим. В § 1.5 излагается метод удаления I-факторов. Этот метод, по существу, использовался Байнеке и Фиори-ни в^ при доказательства несуществования критических граЬов с чётным числом вершин, меньшим чем 12, и З-кригических (с А(G ) = 3 графов с 12 вершинами. Он опирается на следующие два утвервдения, доказанные Визингом в^ :

Утверждение I.I7. Пусть J - любое независимое множество рёбер Сд -графа G . Тогда X ( 0-1 ) = # ' ( G ) - I, где через G ~ 1 обозначен подграф, образующийся из G после удаг-тения I .

Утверждение Î.I8. Пусть ( G ) = Л , X'^ûJ^A+I. Тогда граф G содержит Ск -подграф для каждого К = 2,...,Д .

Применительно к графам с чётным числом вершин данные утверждения имеют следствием результат, на котором базировались доказательства в*, но не сформулированный Байнеке и Фиорини явно:

Следствие I.I9. Пусть Сд -граф G шеет I-фантор f* Тогда г дграф С- - F содержит Сд. -подграф.

В соответствии со следствием I.I9 идею метода удаления I-факторов можно сформулировать так: выяснить, содержит ли подграф G - F графа G с чётным числом вершин из класса Пд.

1 Be in eke L.W., Fiorim S. On smalt graphs critical with respect to edge -colourings iïDhcr. Matk-Ш.-М.-Р. ювш

Визинг В.Г. Критические графы с данным хроматическим классом // Дискр. анализ. - 1965. - Вып. 5. - С. 9 - 17.

Сь-1 -подграф для всякого 1-фактора р , наличие которого в £ установлено. Если найдётся тшюй 1-фактор р в О , что подграф О - р не содержит Сй./ -подграфа, то в силу следствия 1.19 граф £ не является критически!. Еолво того, как показывает другое следствие из утверждений 1.17, 1.18, он принадлежит тогда классу I:

Следствие 1,20. Пусть граф & б 77д имеет 1-фактор р такой, что подграй (г-Р не содеряпт Сд./ -подграфа. Тогда ;*'(&> = Л СО.

Рассматривается бесконечное семейство графов из класса 77/> с к вершинами степени 2 и 3 к вершинаш степени 4, гдэ к^ 3. Теорема 1.8 позволяет отбросить, как заведомо но критические, все графы из этого семейства, у которых хотя бы для одной пары вершин степени 2 и. и ху имеет место неравенство р^ ( ^'3. Ос-

тальные графы могут быть исследованы на критичность методом удаления 1-факторов, наличие которых устанавливается с помощью критерия, опирящегося на теорему Холла о системах различных представителей в её теоретико-графовой форме ( см.* ). Сложность данного исследования зависит от числа 1-фажторов в графе и оценивается сверху величиной порядка 4* . Проводится пример подсемейства графов, име--дпих не менее 2^ 1-факторов. Это говорит о том, что уже при Л - 4 1/етод удаления 1-факторов является экспоненциально сломшм относительно числа верглш графа.

§ 1.6 посвящен методу удаления цветных классов, имеющее некоторые преимущества по сравнению с предыдущим методом: во-первых, он примени.! к графам как с чётным, так и с нечётким числом вершин; во-вторых, он не требует обоснования наличия 1-фактора в графе. Этот мзтод опирается на результат, который выводится, как следствие, из утверждений 1.17 и 1.18:

СяедстЕие 1.21. Пусть ^С ( & ) - А (&)+!■ и граф &■ допускает напряжённую раскраску <^1/ (Р в света ОД,..,, Д , и пусть - цветной класс в этой раскраске, соответствующий

цвету I ( I 4Д ) ( множество всех рёбер, раскрашенных в цвет I ) такому, чго^_ Д ( & - Е^ ) = А - I. Тогда подграф & - £<• содеряит СА.( -подграф , причём ребро Ш

е Е< Н[).

1 Свами ГЛ., Тхуласпраман К. Графы, сети и алгоритмы. - М.: Мир, 1964. - 455 с. - теорема 8.13.

Таким образом, метод заключается в следуицем: I) предполагается, что граф б из класса 7Гд допускает напряжённую раскраску для каждого ребра (и,1*)в Е ( С ) ( поскольку иначе граф О заведомо не является критическим ); 2) для каждого ребра (Ц.1?-) графа б и для всякого цветного класса ( 14 £4Д)

в раскраске Ч'а,^- , удаление которого понижает максимальную степень Д ( & ) на единицу, проверяется, содержит ли подграф & -- С*.1 -подграф Н[ такой, что (Е ( Н£ ). Если

это требование не выполняется котя бы дая одного ребра то,

как показывает ещё одно следствие из утверждений 1.17 и 1.18, граф & раскрашивается в А цветов: ;

Следствг 1,22. Пусть траф & £ Яд допускает напряжённую раскраску Уи,су- в Цвета 0,1,...,д , в которой найдётся цветной класс Е-1 , соответствующий некоторому цвету с ( I 6 Д), такой, что А { & - Ес ) = А - I и ребро Ш ,00 не принадлежит никакому Сд-подграфу графа £ - . Тогда %'{ & ) = А .

Доказывается нижняя оценка числа Сд -подграфов в Сд. --графе ( I ^ ^ 4 А - 2 ), частный случай которой ( при £ = I ) представляет собой оценку сложности метода удаления цветных классов:

Теорема 1.23. Пусть и и I?- - смежные вершины Сд -графа О и пусть с!ед £ (и) =к Мед& ((*-) =д-к + 2 , где ^ ^ А , 0 4 р4 к - 2. Тогда ребро ( и, 19-) принадлежит не менее чем Сд £ -подграфам графа £ , где

'(е-д^-.Ц" 'Щ'^рУ

14 I 4 Д - 2; (^У число сочетаний из д: по у ,/".£] и 5дп (X 3 соответственно - целая часть п знак X •

-53П<

д-к+1

ПАВА 2. Устанавливается несуществование /2-вершишшх Сц --графов ( в § 2.1 ) и некоторых 12-вершинных С5 -графов ( в § 2.2 ).

При рассмотрении 12-вершинных графов из класса ТТц возникает шесть случаев, в которых эти графы могут быть критическими.

Пазовом степенным списком графа G выражение О °1П'... ДПл , где А = Л ( G ), /lj / 0 - число вершин степени j в & ( если

flj = О, то подвыражение j nJ опускается ). Тогда этим случаям соответствуют ппсть возмогших степенных списков для 12-воршшшнх графов из класса ТТц , исследуемых на критичность: Iй , 23 4Э , 22 З2 4а , 2{ 3* 47 , З6 46 , 48 . Несуществование критических Грефов со степонннм списном 2^ 4е устанавливается в рамках структурно-метрического подхода ( с использованием теоремы 1.9 ). Доказательство несуществования критических графов с остальными пятью степенными списка!® использует либо метод удаления 1-факторов ( для грсфов со степенными списками 23 43 , 22 З2 4& , З6 46 ), либо метод удаления цветных классов ( для графэв со степенным списком 2' З1' 47 ), либо оба эта метода ( для градов со степенным списком 3^4®). Кромо того, доказывается:

Теорема 2.1. Всякий 12-вер;шшьй грай из класса ТТ/, , дугя которого справедливы заключения теорем 1.8 и 1,11, не содеряащпй С^ -подграфа К5-в , раскрашивается в 4 цвета.

L'. § 2.2 в вгатегос структурно-метрического подхода устанавлпва-5 -гргтфоз со степенными списками 2 5 , 2г Зг , 25 4' 5â , 2г 3' 42 Б7 , ?J 3Z 43 5б , 2' З"3 4* 57 , З6 56 , З-5" 5? , а таюж С5 -графов с.о степенными списками з'' 56 , 3^4256 , 2' З2 4' 5 8 , облздамиих веерной симметрией 1-го порядка ( с использованием теорем 1.8, 1.9 и I.16 ).

ГЛАВА 3. Приводится алгоритм, позволяющий определить, принадлежи' ли граф & с Д ( &- ) = 3 классу 1, классу 2, и является ли он Cj -графом. Опаливается его сложность для графов из класса 7Г3 . В основе алгоритма летит следущее утверждение:

Тропека 3.1. Пусть G - граф с А ( & ) - 3. Тогда:

1) Item в G- существует паросочеталие J , покрывающее все вершины стопит 3 и такое, что подграф G- - J не содержг пимов нечётной длины, то X ( G ) = 3;

2) Если идя любого паросочетанкя J в G . покрывающего все вершины степени 3, подграф G -1 содержат цикл нечётной Ллшш, то ( G ) = 4;

3) Если дел любого ребра { £ ( G ) найдётся паросоче-талио I в & , полрывпицее всо вершины степени 3 в такое, что ( U , (?•) принадлежит единственному циклу нечётной длины в подграфе

G -1 .то, при условии, что X (G ) = 4, б- является G^-грпфом.

Сложность алгоритма для графов из класса 77"з оценивается сверху величиной порядка О (П33Пз), гдо П и Пз - соответственно числа вершин и вершин степени 3 в графе.

В заключение автор выражает глубокую благодарность научному руководителю доценту Г.П. Гаврилову.

Работы автора но тема диссертации

1. Цузычук И.А. О несуществовании некоторых 4-критических графов двенадцат го порядка / Вестн. МГУ. Сер. 1,1 Математика, механика. - 1989. - № 6. - С. 58 - 60.

2. Музычук И.А.' 0 несуществовании чётных 4-критическлх графов по- . рядка 12 / Дискретная математика. - 1390. - Т. 2. - Вып. 4. -С. 47 - 59.

3. Гаврилов Т.П., Музычук И.А. Об одном метрическом свойстве графов, критических по рёберной раскраске / Труды Второй Межд. Конф. по дискр. математике и её применениям. - Еяагоевград, 5-10 июня 1990. - С. 14.

4. Гаврилов Г.П., Музычук И.А. О некоторых метрических свойствах графов, критических по рёберной раскраске / ¡ЛГУ. - М., 1990. -14 с. - Деп. в ВШИ1И 01.08.90, № 4377-В90.

5. Музычук И.А. О несуществовании 4-критяческих графов порядка 12 , МГУ. - М., 1990. - 23 с. - Деп. в ВИНИТИ 01.08.90, Я 4376-В90.

Подп. в'печ. 06.11.91 г. Тирах 100 экз. Заказ 1С 9488

Централизованная типография ГА "Союзстройматериалов"