Дефектная раскраска (:ysytmugx jgvtjgvtg)
Дефектная раскраска — это вариант правильной раскраски вершин. В правильной раскраске вершин вершины раскрашиваются так, что никакая из смежных вершин не имеют одного цвета. При дефектной раскраске, с другой стороны, вершинам разрешено в известной мере иметь соседей того же цвета.
История
[править | править код]Дефектную раскраску предложили почти одновременно Бурр и Джексон, Харари и Джонс, Ковины и Вудал[1]. Обзор этих и связанных раскрасок дала Марики Фрик[2]. Ковины (Л. И Р.) и Вудал[1] сфокусировались на графах, вложенных в поверхности и дали полное описание всех k и d, таких что любой планарный граф (k, d)-раскрашиваем. А именно, не существует d таких, что любой планарный граф (1, d)- или (2, d)-раскрашиваем. Существуют планарные графы, которые не (3, 1)-раскрашиваемы, но любой планарный граф имеет (3, 2)-раскраску. Вместе с (4, 0)-раскраской, вытекающей из теоремы о четырёх красках, это решает задачу о дефектном хроматическом числе для плоскости. Пох[3] и Годдар[4] показали, что любой планарный граф имеет специальную (3,2)-раскраску, в которой каждый класс цвета является линейным лесом, и это можно получить из более общего результата Вудала.
Для поверхностей общего вида было показано, что для любого рода существует число такое, что любой граф на поверхности рода (4, k)-раскрашиваем[1]. Этот результат улучшил до (3, k)-раскрашиваемости Дэн Арчдикон[5].
Для графов общего вида результат Ласло Ловаса 1960-х годов, который был переоткрыт много раз[6][7][8], даёт алгоритм со временем работы для дефектной раскраски графов с максимальной степенью .
Определения и терминология
[править | править код]Дефектная раскраска
[править | править код]-раскраска графа G — это раскраска вершин графа в k цветов так, что каждая вершина v имеет максимум d соседей того же цвета, что и вершина v. Мы считаем k положительным целым числом (бессмысленно рассматривать случай с нулевым числом цветов, k=0), а d считаем неотрицательным целым. Тогда (k, 0)-раскраска эквивалентна правильной раскраске вершин[9].
d-дефектное хроматическое число
[править | править код]Минимальное число цветов k, требующихся для получения (k, d)-раскраски графа G, называется d-дефектным хроматическим числом, [10].
Неправильность вершины
[править | править код]Пусть c будет раскраской вершин графа G. Неправильностью вершины v графа G, это число соседей вершин v, которые имеют тот же цвет, что и v. Если неправильность вершины v равна 0, тогда говорят, что вершина v правильно раскрашена[1].
Неправильность раскраски вершины
[править | править код]Пусть c будет раскраской вершин графа G. Неправильность раскраски c — это максимум неправильностей всех вершин графа G. Следовательно, неправильность правильной раскраски вершин равна 0[1].
Пример
[править | править код]Пример дефектной раскраски цикла с пятью вершинами показан на рисунке. Первый пятиугольник является примером правильной раскраски, или (k, 0)-раскраски. Второй пятиугольник является примером (k, 1)-раскраски, а третий — примером (k, 2)-раскраски. Заметьте, что
Свойства
[править | править код]- В терминах теории графов, каждый класс правильной раскраски вершин образует независимое множество, в то время как каждый класс дефектной раскраски образует подграф степени, не превосходящей d[11].
- Если граф (k, d)-раскрашиваем, то он (k′, d′)-раскрашиваем для каждой пары (k′, d′) такой что и [1].
Некоторые результаты
[править | править код]Любой внешнепланарный граф (2,2)-раскрашиваем
[править | править код]Доказательство: Пусть будет связным внешнепланарным графом. Пусть будет произвольной вершиной графа . Пусть будет набором вершин графа которые находятся на расстоянии от . Пусть будет , подграфом, порождённым набором вершин . Предположим, что содержит вершину степени 3 или более, тогда он содержит в качестве подграфа. Тогда мы стягиваем все рёбра графа , чтобы получить новый граф . Следует заметить, что графа связен, поскольку любая вершина в смежна вершине в . Следовательно, стягиванием всех рёбер, упомянутых выше, мы получим граф , такой что подграф графа заменяется одной вершиной, которая смежна всем вершинам в . Тогда граф содержит в качестве подграфа. Но любой подграф внешнепланарного графа внешнепланарен, и любой граф, полученный стягиванием рёбер внешнепланарного графа, является внешнепланарным. Из этого следует, что внешнепланарен, чего не может быть. Следовательно, никакой из графов не содержит вершин степени 3 и выше, откуда следует, что (k, 2)-раскрашиваем.
Следует также заметить, что никакая вершина из не смежна с какой-либо вершиной или , следовательно вершины могут быть выкрашены в синий цвет, если нечётно, или в красный цвет, если чётно. Следовательно, мы получили (2,2)-раскраску графа [1].
Следствие: Любой планарный граф (4,2)-раскрашиваем. Это следует из того, что если планарен, то любой (как выше) внешнепланарен. Следовательно, любой (2,2)-раскрашиваем. Следовательно, каждая вершина может быть раскрашена в красный или синий цвет, если чётно и в зелёный и жёлтый цвет, если нечётно, что даёт (4,2)-раскраску графа .
Графы без полных миноров
[править | править код]Для любого целого существует целое , такое что любой граф без миноров является -раскрашиваемым[12].
Вычислительная сложность
[править | править код]Дефектная раскраска вычислительно трудна. Задача определения, позволяет ли данный граф (3,1)-раскраску NP-полна, даже в случае, когда имеет максимальную степень вершины 6 или когда он планарен и имеет максимальную степень вершин 7[13].
Приложения
[править | править код]Пример приложения дефектной раскраски — задача расписания, в которой вершины представляют работы (скажем, пользователи компьютерной системы), а рёбра представляют конфликты (необходимость доступа к одним и тем же файлам). Разрешение дефекта означает допустимость некоторого порога конфликта — каждый пользователь может, скажем, принять максимально допустимое замедление, вызванное извлечением данных из двух конфликтных файлов, но не более[14].
Примечания
[править | править код]- ↑ 1 2 3 4 5 6 7 Cowen, Cowen, Woodall, 2006, с. 187–195.
- ↑ Frick, 1993, с. 45–57.
- ↑ Poh, 1990, с. 73–75.
- ↑ Goddard, 1991, с. 91–94.
- ↑ Archdeacon, 1987, с. 517–519.
- ↑ Bernardi, 1987, с. 95–96.
- ↑ Borodin, Kostochka, 1977, с. 247–250.
- ↑ Lawrence, 1978, с. 61–68.
- ↑ Cowen, Goddard, Jesurum, 1997, с. 205–219.
- ↑ Frick, Henning, 1994, с. 151–158.
- ↑ Cowen, Goddard, Jesurum, 1997, с. 548–557.
- ↑ Edwards, Kang, Kim, Oum, Seymour, 2015, с. 2385–2388.
- ↑ Angelini, Bekos, De Luca и др., 2017, с. 313–340.
- ↑ Cowen, Goddard, Jesurum (SODA), 1997, с. 548–557.
Литература
[править | править код]- Marietjie Frick. A Survey of (m,k)-Colorings. — Annals of Discrete Mathematics. — 1993. — Т. 55. — ISBN 9780444894410. — doi:10.1016/S0167-5060(08)70374-1.
- Poh K. S. On the linear vertex-arboricity of a planar graph // Journal of Graph Theory. — 1990. — Март (т. 14, вып. 1). — doi:10.1002/jgt.3190140108.
- Wayne Goddard. Acyclic colorings of planar graphs // Journal Discrete Mathematics. — 1991. — Август (т. 91, вып. 1). — doi:10.1016/0012-365X(91)90166-Y.
- Dan Archdeacon. A note on defective colorings of graphs in surfaces // Journal of Graph Theory. — 1987. — Т. 11, вып. 4. — doi:10.1002/jgt.3190110408.
- Claudio Bernardi. On a theorem about vertex colorings of graphs // Discrete Mathematics. — 1987. — Март (т. 64, вып. 1). — doi:10.1016/0012-365X(87)90243-3.
- Borodin O.V, Kostochka A.V. On an upper bound of a graph's chromatic number, depending on the graph's degree and density // Journal of Combinatorial Theory, Series B. — 1977. — Oct–Dec (т. 23, вып. 2–3). — doi:10.1016/0095-8956(77)90037-5.
- Jim Lawrence. Covering the vertex set of a graph with subgraphs of smaller degree // Discrete Mathematics. — 1978. — Т. 21, вып. 1. — doi:10.1016/0012-365X(78)90147-4.
- Cowen L., Goddard W., Jesurum C. E. Coloring with defect // In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97, New Orleans, Louisiana, United States, January 05–07, 1997). — Philadelphia, PA: Society for Industrial and Applied Mathematics, 1997.
- Cowen L., Goddard W., Jesurum C. E. Defective coloring revisited // J. Graph Theory. — 1997. — Т. 24, вып. 3. — doi:10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T.
- Marietjie Frick, Michael Henning. Extremal results on defective colorings of graphs // Discrete Mathematics. — 1994. — Март (т. 126, вып. 1–3). — doi:10.1016/0012-365X(94)90260-7.
- Cowen L. J., Cowen R. H., Woodall D. R. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency // Journal of Graph Theory. — 2006. — Октябрь (т. 10, вып. 2). — doi:10.1002/jgt.3190100207.
- Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, Paul Seymour. A Relative of Hadwiger's Conjecture // SIAM Journal on Discrete Mathematics. — 2015. — Т. 29. — doi:10.1137/141002177. — arXiv:1407.5236.
- Patrizio Angelini, Michael Bekos, Felice De Luca, Walter Didimo, Michael Kaufmann, Stephen Kobourov, Fabrizio Montecchiani, Chrysanthi Raftopoulou, Vincenzo Roselli, Antonios Symvonis. Vertex-Coloring with Defects // Journal of Graph Algorithms and Applications. — 2017. — Т. 21, вып. 3. — С. 313–340. — doi:10.7155/jgaa.00418.
- Nancy J. Eaton, Thomas Hull. Defective list colorings of planar graphs // Bull. Inst. Combin. Appl. — 1999. — Т. 25. — С. 79–87.
- William W., Thomas Hull. Defective Circular Coloring // Austr. J. Combinatorics. — 2002. — Т. 26. — С. 21–32.
Для улучшения этой статьи желательно:
|
На эту статью не ссылаются другие статьи Википедии. |