Общая раскраска с различением соседних вершин
В теории графов полная раскраска — это раскраска вершин и ребер графа такая, что:
(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-total-раскраска), если она обладает следующим дополнительным свойством:
(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-полной раскраски. (Чжан и др. [3] )
- χ в ( G ) ≤ Δ( G ) + 3.
Известно, что гипотеза AVD-тотальной раскраски верна для некоторых классов графов, таких как полные графы . [4] графики с Δ=3, [5] [6] и все двудольные графы . [7]
В 2012 году Хуанг и др. [8] показал, что χ при ( G ) ≤ 2Δ( G )для любого простого графа G с максимальной степенью Δ( G ) > 2.В 2014 году Папайоанну и Рафтопулу [9] описал алгоритмическую процедуру, которая дает 7-AVD-общая раскраска для любого 4-регулярного графа.
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Лу, Синьчжун; Ван, Цзяньфан (2005) Чжан, Чжун-фу; Чен, Ли Цзинвэнь ; , . 3): 289–299. Бибкод : 2005ScChA..48..289Z 03ys0207 doi : 10.1360/ . S2CID 6107913 .
- Халган, Джонатан (2009). «Краткие доказательства полной раскраски, различающей смежные вершины». Дискретная математика . 309 (8): 2548–2550. дои : 10.1016/j.disc.2008.06.002 .
- Чен, Сянъэнь (2008). «По соседней вершине различение суммарных чисел раскраски графов с Дельтой=3». Дискретная математика . 308 (17): 4003–4007. дои : 10.1016/j.disc.2007.07.091 .
- Хуанг, Д.; Ван, В.; Ян, К. (2012). «Примечание о соседней вершине, отличающей общее хроматическое число графов» . Дискретная математика . 312 (24): 3544–3546. дои : 10.1016/j.disc.2012.08.006 .
- Чен, Мейрун; Го, Сяофэн (2009). «Смежное ребро, различающее вершины, и общее хроматическое число гиперкубов». Письма об обработке информации . 109 (12): 599–602. дои : 10.1016/j.ipl.2009.02.006 .
- Ван, Ицяо; Ван, Вэйфан (2010). «Смежная вершина, определяющая полные раскраски внешнепланарных графов». Журнал комбинаторной оптимизации . 19 (2): 123–133. дои : 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. дои : 10.1007/s10878-012-9527-2 . S2CID 254642281 .
- Хуан, Даньцзюнь; Ван, Вэйфан; Ян, Чэнчао (2012). «Примечание о соседней вершине, отличающей общее хроматическое число графов» . Дискретная математика . 312 (24): 3544–3546. дои : 10.1016/j.disc.2012.08.006 .
- Папайоанну, А.; Рафтопулу, К. (2014). «Об AVDTC 4-регулярных графов». Дискретная математика . 330 : 20–40. дои : 10.1016/j.disc.2014.03.019 .
- Луис, Атилио Г.; КАМПОС, Китай; де Мелло, CP (2015). «AVD-тотальное окрашивание равнодольных полных графов». Дискретная прикладная математика . 184 : 189–195. дои : 10.1016/j.dam.2014.11.006 .