Общая окраска смежных вершин - Adjacent-vertex-distinguishing-total coloring

Правильная AVD-полная раскраска полный график K4 с 5 цветами, минимально возможное количество.

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

(1). никакие соседние вершины не имеют одинаковый цвет;

(2). никакие соседние кромки не имеют одинаковый цвет; и

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

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

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

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

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

В общее хроматическое число прилежащих вершин χв(грамм) графа грамм это наименьшее количество цветов, необходимых для полного раскраски AVD грамм.

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

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

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

χв(грамм) ≤ Δ (грамм) + 3.

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

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

Примечания

  1. ^ Чжан 2005.
  2. ^ Чжан 2005, стр. 290.
  3. ^ Чжан 2005, стр. 299.
  4. ^ Халган 2009, стр. 2.
  5. ^ Халган 2009, стр. 2.
  6. ^ Чен 2008.
  7. ^ Чжан 2005.
  8. ^ Хуанг2012
  9. ^ Папайоанну, 2014

Рекомендации

  • Чжан, Чжун-фу; Чен, Сян-эн; Ли, Цзинвэнь; Яо, Бин; Лу, Синьчжун; Ван, Цзяньфан (2005). «О тотальной раскраске графов с выделением смежных вершин». Наука Китай Математика. 48 (3): 289–299. Дои:10.1360 / 03ys0207.
  • Халган, Джонатан (2009). «Краткие доказательства для смежных раскрасок с различением вершин». Дискретная математика. 309 (8): 2548–2550. Дои:10.1016 / j.disc.2008.06.002.
  • Чен, Сянъен (2008). «На соседней вершине различение общих номеров раскраски графов с Delta = 3». Дискретная математика. 308 (17): 4003–4007. Дои:10.1016 / j.disc.2007.07.091.
  • Huang, D .; Wang, W .; Ян, К. (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-х.
  • П. де Мелло, Селия; Педротти, Вагнер (2010). «Полная раскраска графов безразличия с выделением смежных вершин» (PDF). Matematica Contemporanea. 39: 101–110.[постоянная мертвая ссылка ]
  • Ван, Вэйфань; Хуанг, Даньцзюнь (2012). «Смежная вершина, отличающая тотальную раскраску плоских графов». Журнал комбинаторной оптимизации. 27 (2): 379. Дои:10.1007 / s10878-012-9527-2.
  • Чен, Сян-эн; Чжан, Чжун-фу (2008). «Номера AVDTC обобщенных графов Халина с максимальной степенью не менее 6». Acta Mathematicae Applicatae Sinica. 24 (1): 55–58. Дои:10.1007 / s10878-012-9527-2.
  • Хуанг, Даньцзюнь; Ван, Вэйфань; Ян, Чэнчао (2012). «Замечание о соседней вершине, обозначающее общее хроматическое число графов». Дискретная математика. 312 (24): 3544–3546. Дои:10.1016 / j.disc.2012.08.006.
  • Papaioannou, A .; Рафтопулу, К. (2014). «О AVDTC 4-х регулярных графиков». Дискретная математика. 330: 20–40. Дои:10.1016 / j.disc.2014.03.019.
  • Луис, Атилио Дж .; Campos, C.N .; де Мелло, К. (2015). «AVD-тотальная раскраска полных равнодольных графов». Дискретная прикладная математика. 184: 189. Дои:10.1016 / j.dam.2014.11.006.