Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Правильная общая окраска клетки Фостера в 6 цветов. Всего хроматического число этого графа равно 6 , так как степень каждой вершины 5 (5 смежное ребро +-вершина = 6).

В теории графов , общая окраска представляет собой тип раскраски графа на вершинах и ребрах графа. При использовании без каких-либо уточнений общая окраска всегда считается правильной в том смысле, что никакие смежные кромки, кромки и их концевые вершины не имеют одного цвета. Всего хроматического числа χ "( G ) графа G является наименьшее количество цветов , необходимых в любой общей окраски G .

Общий график Т = Т ( G ) графа G представляет собой график , такой , что (я) множество вершин Т соответствует вершин и ребер G и (II) , две вершины смежны в T тогда и только тогда , когда соответствующие им элементы являются либо смежно или случай в G . Тогда общая окраска G становится (правильная) вершинная окраской из Т ( G ). Тотальная раскраска - это разбиение вершин и ребер графа на полные независимые множества .

Некоторые неравенства для χ ″ ( G ):

  1. χ ″ ( G ) ≥ Δ ( G ) + 1.
  2. χ ″ ( G ) ≤ Δ ( G ) + 10 26 . (Моллой, Рид 1998)
  3. χ ″ ( G ) ≤ ∆ ( G ) + 8 ln 8 (∆ ( G )) для достаточно большого ∆ ( G ). (Хинд, Моллой, Рид, 1998)
  4. χ ″ ( G ) ≤ ch ′ ( G ) + 2.

Здесь Δ ( G ) - максимальная степень ; и ch ′ ( G ) - возможность выбора ребер .

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

Полная раскраска верхней границы максимальной степени - сложная задача, ускользавшая от математиков в течение 50 лет. Тривиальная нижняя граница для χ ″ ( G ) равна ∆ ( G ) + 1. Некоторым графам, таким как циклы длины и полные двудольные графы вида, требуется ∆ ( G ) + 2 цвета, но не найдено графа, который требовал бы большего количества цветов. . Это приводит к предположению, что каждому графику требуется Δ ( G ) + 1 или Δ ( G ) + 2 цвета, но не более:

Гипотеза тотальной раскраски ( Бехзад , Визинг).

По-видимому, термин «полная окраска» и утверждение гипотезы о полной окраске независимо друг от друга вводились Бехзадом и Визингом во многих случаях между 1964 и 1968 годами (см. Jensen & Toft). Известно, что эта гипотеза верна для нескольких важных классов графов, таких как все двудольные графы и большинство плоских графов, кроме графов с максимальной степенью 6. Плоский случай может быть завершен, если гипотеза Визинга о плоских графах верна. Кроме того, если гипотеза о раскраске списка верна, то

Получены результаты, относящиеся к полной окраске. Например, Килакос и Рид (1993) доказали, что дробное хроматическое число полного графа графа G не превосходит Δ ( G ) + 2.

Ссылки [ править ]