Cтраница 1
Реберная раскраска называется правильной, если любые два смежных ребра имеют разные цвета. Реберная раскраска с минимальным числом цветов называется минимальной. [1]
Реберной раскраской ( или раскраской по Тейту) графа О назовем отображение множества Е ( 0) в Т, при котором ребра, инцидентные одной и той же вершине, отображаются в три различных цвета. Из определения следует, что граф, содержащий петлю, не допускает реберной раскраски. [2]
Напомним, что реберная раскраска графа G - это такая раскраска его ребер, при которой любые два смежных ребра имеют разные цвета. Хроматическим индексом Xe ( G) графа G называется наименьшее число красок в его реберных раскрасках. [3]
Пусть граф допускает кубируемую реберную раскраску. Тогда, сопоставив каждой окраске порядковый номер разряда двоичного вектора и приписав одной из вершин графа произвольный двоичный вектор, размерность которого равна числу красок, получим взаимно однозначное соответствие между вершинами графа и двоичными векторами, при котором векторы, соответствующие смежным вершинам графа, отличаются ровно в одном разряде. [4]
Граф Петерсена не имеет реберной раскраски. [5]
Примером графа, не допускающего реберной раскраски, является, как следует из теорем IX. [6]
Каждый цветной класс ребер в допустимой реберной раскраске является, конечно же, паросочетанием. [7]
Предположим, что у графа Петерсена есть реберная раскраска, и обозначим ее через I. [8]
Таким образом, из теоремы Кенига о реберной раскраске вытекает приведенный выше результат. [9]
Пусть В - бонд графа О, - реберная раскраска этого графа, па, щ и пу - количество ребер бонда В, которые при раскраске I получают цвет а, р и у соответственно. Тогда числа па, пр и пу имеют одинаковую четность. [10]
Этот бесхитростно звучащий результат может нас сразу ввести в область реберных раскрасок - еще одну область многообразных и важных исследований в теории графов. Допустимой реберной раскраской произвольного графа G ( двудольного или нет) называют присваивание ( приписывание, назначение) целых чисел ( цветов, красок) ребрам графа G таким образом, чтобы никакие два смежных ребра не были одинакового цвета. [11]
Снарком будем называть связный кубический граф, который не имеет реберной раскраски и бонда, содержащего меньше четырех ребер. Простейшим примером снарка является граф Петерсена. Если граф не допускает реберной раскраски, но имеет бонд В из двух или трех ребер, то этот граф легко редуцируется к меньшему, являющемуся остаточным графом бонда В. Указанный случай очень прост и мы его детально не рассматриваем. [12]
Из этого определения следует, что минимальное число цветов в правильной реберной раскраске оценивается снизу степенью графа, т.е. максимальной степенью вершин. [13]
Сначала установим лемму, которая дает возможность расширять ( увеличивать, улучшать) частичные реберные раскраски графа. [14]
Тогда, если каждый из двух остаточных графов Н и К бонда В допускает реберную раскраску, то и граф О допускает реберную раскраску. [15]