Полная окраска
-
Определение полной раскраски
- Полная раскраска – это раскраска вершин и ребер графа, где ни соседние ребра, ни вершины, ни ребро и конечная вершина не имеют одинаковый цвет.
-
Общее хроматическое число
- Общее хроматическое число θ”(G) – это минимальное количество цветов, необходимых для полной раскраски графа G.
-
Граф T и полная раскраска
- Граф T – это граф, вершины которого соответствуют вершинам и ребрам G, а смежные вершины в T соответствуют смежным элементам в G.
- Полная раскраска G становится вершинной раскраской T.
-
Неравенства для χ”(G)
- Существуют неравенства, связывающие θ”(G) с максимальной степенью Δ(G) и другими параметрами графа.
-
Графы с известными ограничениями
- Некоторые графики, такие как циклы и полные двудольные графы, требуют Δ(G) + 1 или Δ(G) + 2 цветов, но не больше.
-
Гипотеза полной раскраски
- Гипотеза о полной раскраске утверждает, что для любого графа требуется либо Δ(G) + 1, либо Δ(G) + 2 цвета.
- Гипотеза была независимо сформулирована Бехзадом и Визингом в 1960-х годах.
-
Важность гипотезы
- Гипотеза имеет значение для многих классов графов, включая двудольные и плоские графы, за исключением графов с максимальной степенью 6.
-
Планарный случай
- Планарный случай может быть полностью решен, если гипотеза Визинга о плоских графах верна.
-
Связь с другими результатами
- Были получены результаты, связанные с дробным хроматическим числом и другими параметрами графа.
Полный текст статьи: