В теории графов , общая окраска представляет собой тип раскраски графа на вершинах и ребрах графа. При использовании без каких-либо уточнений общая окраска всегда считается правильной в том смысле, что никакие смежные кромки, кромки и их концевые вершины не имеют одного цвета. Всего хроматического числа χ "( G ) графа G является наименьшее количество цветов , необходимых в любой общей окраски G .
Общий график Т = Т ( G ) графа G представляет собой график , такой , что (я) множество вершин Т соответствует вершин и ребер G и (II) , две вершины смежны в T тогда и только тогда , когда соответствующие им элементы являются либо смежно или случай в G . Тогда общая окраска G становится (правильная) вершинная окраской из Т ( G ). Тотальная раскраска - это разбиение вершин и ребер графа на полные независимые множества .
Некоторые неравенства для χ ″ ( G ):
- χ ″ ( G ) ≥ Δ ( G ) + 1.
- χ ″ ( G ) ≤ Δ ( G ) + 10 26 . (Моллой, Рид 1998)
- χ ″ ( G ) ≤ ∆ ( G ) + 8 ln 8 (∆ ( G )) для достаточно большого ∆ ( G ). (Хинд, Моллой, Рид, 1998)
- χ ″ ( 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.
Ссылки [ править ]
- Хинд, Хью; Моллой, Майкл; Рид, Брюс (1998). «Полная раскраска Δ + поли (log Δ) цветов». SIAM Journal on Computing . 28 (3): 816–821. DOI : 10,1137 / S0097539795294578 .
- Дженсен, Томми Р .; Тофт, Бьярн (1995). Задачи раскраски графов . Нью-Йорк: Wiley-Interscience. ISBN 0-471-02865-7 .
- Килакос, Кириакос; Рид, Брюс (1993). «Дробная раскраска тотальных графов». Combinatorica . 13 (4): 435–440. DOI : 10.1007 / BF01303515 .
- Моллой, Майкл; Рид, Брюс (1998). «Оценка общего хроматического числа». Combinatorica . 18 (2): 241–280. DOI : 10.1007 / PL00009820 . ЛВП : 1807/9465 .