Loading AI tools
Из Википедии, свободной энциклопедии
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.
Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G.
Тотальным графом T = T(G) графа G называется граф, в котором
При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа.
Несколько свойств χ″(G):
Здесь Δ(G) — это максимальная степень, а ch′(G) — индекс предписанной раскраски рёбер.
Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок. Следующий шаг — это рассмотрение верхних границ тотального хроматического числа в терминах максимальной степени по аналогии с теоремами Брукса или Визинга. Оказалось, что определение верхних границ тотальной раскраски, как функции от максимальной степени, является сложной задачей и ускользает от математиков вот уже 40 лет.
Наиболее известная догадка выглядит так:
Гипотеза о тотальной раскраске.
По всей видимости, термин «тотальная раскраска» и формулировку гипотезы независимо предложили Бехзад[англ.] и Визинг в многочисленных публикациях между 1964 и 1968 годами (смотри книгу Йенсена и Тофта[3] для деталей).
Известно, что гипотеза справедлива для нескольких важных классов графов, таких как двудольные графы и большинство планарных графов, за исключением графов с максимальной степенью 6. Случай планарных графов будет решён, если будет доказано, что гипотеза Визинга о планарных графах верна. Также, если гипотеза о предписанной раскраске рёбер справедлива, то χ″(G) ≤ Δ(G) + 3.
Были получены некоторые результаты относительно тотальной раскраски. Например, Килакос и Рид[4] доказали, что дробный хроматический индекс тотального графа для графа G не превосходит Δ(G) + 2.
Упомянем также следующую связь рёберного графа и тотального графа:
T(G) является эйлеровым в том и только в том случае, когда L(G) эйлеров.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
