Точная окраска

В теории графов точная раскраска — это (правильная) раскраска вершин , при которой каждая пара цветов появляется ровно на одной паре соседних вершин.То есть это разбиение вершин графа на непересекающиеся независимые множества так, что для каждой пары различных независимых множеств в разбиении существует ровно одно ребро с концами в каждом множестве. ^[1]^[2]

Полные графы, отряды и туры Эйлера

Каждый n -вершинами полный граф Kn _с имеет точную раскраску в n цветов, полученную путем присвоения каждой вершине отдельного цвета.Каждый граф с точной раскраской в n -цветах может быть получен как отделение полного графа, графа, полученного из полного графа путем разделения каждой вершины на независимое множество и пересоединения каждого ребра, инцидентного вершине, ровно с одним из членов соответствующее независимое множество. ^[1]^[2]

Когда k — нечетное число , путь или цикл с ${\tbinom {k}{2}}$ ребра имеет точную раскраску, полученную путем формирования точной раскраски полного графа K _k и последующего нахождения эйлерова обхода этого полного графа. Например, путь с тремя ребрами имеет полную 3-раскраску. ^[2]

Сопутствующие виды окрашивания

Точные раскраски тесно связаны с гармоничными раскрасками (раскрасками, в которых каждая пара цветов встречается не более одного раза) и полными раскрасками (раскрасками, в которых каждая пара цветов встречается хотя бы один раз). Ясно, что точная окраска — это окраска одновременно гармоничная и завершенная. Граф G с n вершинами и m ребрами имеет гармоничную k -раскраску тогда и только тогда, когда $m\leq {\tbinom {k}{2}}$ и граф, образованный из G добавлением ${\tbinom {k}{2}}-m$ изолированные ребра имеют точную раскраску. Граф G с теми же параметрами имеет полную k -раскраску тогда и только тогда, когда $m\geq {\tbinom {k}{2}}$ и существует подграф H графа G с точной k -раскраской, в котором каждое ребро G − H имеет концы разной раскраски. Необходимость условия на ребрах G − H показана на примере четырехвершинного цикла, который имеет подграф с точной 3-раскраской (трехреберный путь), но не имеет полной 3-раскраски сам. ^[2]

Вычислительная сложность

NP -полно определить, имеет ли данный граф точную раскраску, даже в том случае, если граф является деревом . ^[1]^[3] Однако проблема может быть решена за полиномиальное время для деревьев ограниченной степени . ^[1]^[4]

Ссылки

^ Jump up to: ^а ^б ^с ^д Эдвардс, Кейт (2005), «Отряды полных графов», Combinatorics, Probability and Computing , 14 (3): 275–310, doi : 10.1017/S0963548304006558 , MR 2138114 , S2CID 31563931 .
^ Jump up to: ^а ^б ^с ^д Эдвардс, Кейт (2010), «Ахроматическое число фрагментируемых графов», Journal of Graph Theory , 65 (2): 94–114, doi : 10.1002/jgt.20468 , MR 2724490 .
^ Эдвардс, Кейт; МакДиармид, Колин (1995), «Сложность гармоничной окраски деревьев», Discrete Applied Mathematics , 57 (2–3): 133–144, doi : 10.1016/0166-218X(94)00100-R , MR 1327772 .
^ Эдвардс, Кейт (1996), «Гармоничное хроматическое число деревьев ограниченных степеней», Combinatorics, Probability and Computing , 5 (1): 15–28, doi : 10.1017/S0963548300001802 , MR 1395690 , S2CID 860190 .

[e05-1] Jump up to: ^а ^б ^с ^д Эдвардс, Кейт (2005), «Отряды полных графов», Combinatorics, Probability and Computing , 14 (3): 275–310, doi : 10.1017/S0963548304006558 , MR 2138114 , S2CID 31563931 .

[e10-2] Jump up to: ^а ^б ^с ^д Эдвардс, Кейт (2010), «Ахроматическое число фрагментируемых графов», Journal of Graph Theory , 65 (2): 94–114, doi : 10.1002/jgt.20468 , MR 2724490 .

[3] Эдвардс, Кейт; МакДиармид, Колин (1995), «Сложность гармоничной окраски деревьев», Discrete Applied Mathematics , 57 (2–3): 133–144, doi : 10.1016/0166-218X(94)00100-R , MR 1327772 .

[4] Эдвардс, Кейт (1996), «Гармоничное хроматическое число деревьев ограниченных степеней», Combinatorics, Probability and Computing , 5 (1): 15–28, doi : 10.1017/S0963548300001802 , MR 1395690 , S2CID 860190 .

[1]

[2]

[3]

[4]