Смежная-вершинная-различающая-общая окраска

В теории графов полная раскраска — это раскраска вершин и ребер графа, при которой:

(1) ни одна из смежных вершин не имеет одинакового цвета;

(2) ни одно из смежных ребер не имеет одинакового цвета; и

(3) ни одно ребро и его конечные вершины не имеют одинакового цвета.

В 2005 году Чжан и др. ^[1] добавили ограничение к определению общей окраски и предложили новый тип окраски, определяемый следующим образом.

Пусть G = ( V , E ) — простой граф, снабженный полной раскраской φ, и пусть u — вершина графа G . Набор цветов, встречающийся в вершине u, определяется как C ( u ) = { φ ( u )} ∪ { φ ( uv ) | uv ∈ E ( G )}. Две вершины u , v ∈ V ( G ) различимы , если их наборы цветов различны, т. е. C ( u ) ≠ C ( v ).

В теории графов полная раскраска называется полной раскраской, различающей смежные вершины (полной раскраской AVD), если она обладает следующим дополнительным свойством:

(4) для любых двух смежных вершин u , v графа G их наборы цветов отличны друг от друга, т. е. C ( u ) ≠ C ( v ).

Общее хроматическое число χ, различающее смежные вершины _в ( G ) графа G, — это наименьшее количество цветов , необходимое для полной AVD-раскраски графа G.

Следующая нижняя граница для AVD-полного хроматического числа может быть получена из определения AVD-полной раскраски: если простой граф G имеет две смежные вершины максимальной степени, то χ _в ( G ) ≥ Δ( G ) + 2. ^[2] В противном случае, если простой граф G не имеет двух смежных вершин максимальной степени, то χ _в ( G ) ≥ Δ( G ) + 1.

В 2005 году Чжан и др. определили AVD-общее хроматическое число для некоторых классов графов и на основе своих результатов выдвинули следующее предположение.

Гипотеза AVD-Total-Coloring. (Чжан и др. ^[3] )

χ _при ( G ) ≤ Δ( G ) + 3.

Известно, что гипотеза AVD-Total-Coloring справедлива для некоторых классов графов, таких как полные графы , ^[4] графы с Δ=3, ^{[5] [6]} и все двудольные графы . ^[7]

В 2012 году Хуан и др. ^[8] показали, что χ _в ( G ) ≤ 2Δ( G ) для любого простого графа G с максимальной степенью Δ( G ) > 2. В 2014 году Папаиоанну и Рафтопулу ^[9] описали алгоритмическую процедуру, которая дает 7-AVD-тотальную раскраску для любого 4-регулярного графа.

• Чжан, Чжун-фу; Чен, Сян-энь; Ли, Цзинвэнь; Яо, Бин; Лу, Синьчжун; Ван, Цзяньфан (2005). «О полной раскраске графов, различающей смежные вершины». Наука Китай Математика . 48 (3): 289–299. Бибкод : 2005ScChA..48..289Z. doi : 10.1360/03ys0207 (неактивен 25 сентября 2024 г.). S2CID  6107913.{{cite journal}}: CS1 maint: DOI неактивен по состоянию на сентябрь 2024 г. ( ссылка )
• Hulgan, Jonathan (2009). «Краткие доказательства для смежных вершин-различающих тотальных раскрасок». Дискретная математика . 309 (8): 2548–2550. doi :10.1016/j.disc.2008.06.002.
• Чэнь, Сянъэнь (2008). «О смежных вершинах, различающих общие числа раскрасок графов с Delta=3». Дискретная математика . 308 (17): 4003–4007. doi :10.1016/j.disc.2007.07.091.
• Хуан, Д.; Ван, В.; Янь, Ч. (2012). «Заметка о смежной вершине, различающей общее хроматическое число графов». Дискретная математика . 312 (24): 3544–3546. doi : 10.1016/j.disc.2012.08.006 .
• Чэнь, Мейрун; Го, Сяофэн (2009). «Соседнее вершинно-различающее ребро и общее хроматическое число гиперкубов». Information Processing Letters . 109 (12): 599–602. doi :10.1016/j.ipl.2009.02.006.
• Ван, Ицяо; Ван, Вэйфан (2010). «Смежная вершина, различающая общую раскраску внешнепланарных графов». Журнал комбинаторной оптимизации . 19 (2): 123–133. doi :10.1007/s10878-008-9165-x. S2CID  30532745.
• П. де Мелло, Селия; Педротти, Вагнер (2010). «Общая раскраска графов безразличия с выделением соседних вершин». Математика Современная . 39 : 101–110.
• Ван, Вэйфан; Хуан, Даньцзюнь (2012). «Смежные вершины, различающие общую раскраску планарных графов». Журнал комбинаторной оптимизации . 27 (2): 379. doi :10.1007/s10878-012-9527-2. S2CID  254642281.
• Чэнь, Сян-энь; Чжан, Чжун-фу (2008). «Числа AVDTC обобщенных графов Халина с максимальной степенью не менее 6». Acta Mathematicae Applicatae Sinica . 24 (1): 55–58. doi :10.1007/s10878-012-9527-2. S2CID  254642281.
• Хуан, Даньцзюнь; Ван, Вэйфан; Янь, Чэнчао (2012). «Заметка о смежной вершине, различающей общее хроматическое число графов». Дискретная математика . 312 (24): 3544–3546. doi : 10.1016/j.disc.2012.08.006 .
• Папаиоанну, А.; Рафтопулу, К. (2014). «Об AVDTC 4-регулярных графов». Дискретная математика . 330 : 20–40. doi :10.1016/j.disc.2014.03.019.
• Луис, Атилио Г.; Кампос, Китай; де Мелло, CP (2015). «AVD-тотальная раскраска полных равнодольных графов». Дискретная прикладная математика . 184 : 189–195. дои : 10.1016/j.dam.2014.11.006.