Yonma-yon vertexni ajratib turuvchi-umumiy rang berish - Adjacent-vertex-distinguishing-total coloring

AVD-ning to'liq ranglanishi to'liq grafik K4 5 ta rang bilan, mumkin bo'lgan minimal raqam.

Yilda grafik nazariyasi, a umumiy rang grafaning tepalarida va qirralarida rang berish quyidagicha:

(1). hech qanday qo'shni tepaliklar bir xil rangga ega emas;

(2). bir xil rangga ega qo'shni qirralarning yo'qligi; va

(3). hech qanday chekka va uning endvertlariga bir xil rang berilmagan.

2005 yilda Zhang va boshq.[1] umumiy rang ta'rifiga cheklov qo'shdi va quyidagicha ta'riflangan yangi rang turini taklif qildi.

Ruxsat bering G = (V,E) umumiy rang bilan ta'minlangan oddiy grafik bo'ling va ruxsat bering siz ning tepasi bo'ling G. Ranglar to'plami sodir bo'ladi tepada siz sifatida belgilanadi C(siz) = {φ(siz)} ∪ {φ(uv) | uv ∈ E(G)}. Ikki tepalik siz,v ∈ V(G) bor ajralib turadigan agar ularning rang to'plamlari aniq bo'lsa, ya'ni C(siz) ≠ C(v).

Yilda grafik nazariyasi, umumiy rang an qo'shni-vertex-ajrata oladigan-total-coloring (AVD-total-coloring), agar u quyidagi qo'shimcha xususiyatga ega bo'lsa:

(4). har ikki qo'shni tepalik uchun siz,v grafik G, ularning ranglar to'plamlari bir-biridan ajralib turadi, ya'ni. C(siz) ≠ C(v).

The qo'shni-vertex-ajrata oladigan-total-xromatik son χda(G) grafik G AVD-total-rangida zarur bo'lgan eng kam ranglar G.

AVD-total xromatik sonining quyidagi pastki chegarasini AVD-total-coloring ta'rifidan olish mumkin: Agar oddiy grafik G maksimal darajadagi ikkita qo'shni tepalikka ega, keyin χda(G≥ Δ (G) + 2.[2] Aks holda, agar oddiy grafik bo'lsa G maksimal darajadagi ikkita qo'shni tepalikka ega emas, keyin χda(G≥ Δ (G) + 1.

2005 yilda Zhang va boshq. ba'zi grafikalar sinflari uchun AVD-total-xromatik sonni aniqladi va natijalariga ko'ra ular quyidagilarni taxmin qilishdi.

AVD-Total-Coloring taxmin. (Chjan va boshq.[3])

χda(G≤ Δ (G) + 3.

AVD-Total-Coloring gipotezasi, masalan, ba'zi bir grafikalar sinflari uchun ma'lum to'liq grafikalar,[4] ph = 3 bo'lgan grafikalar,[5][6] va barchasi ikki tomonlama grafikalar.[7]

2012 yilda Huang va boshq.[8] buni ko'rsatdi χda(G≤ 2Δ (G) har qanday oddiy grafik uchun G maksimal daraja bilan Δ (G)> 2. 2014 yilda Papaioannou va Raftopoulou[9] har qanday 4 muntazam grafik uchun 7-AVD-total rang beradigan algoritmik protsedurani tavsifladi.

Izohlar

  1. ^ Jang 2005 yil.
  2. ^ Zhang 2005, p. 290.
  3. ^ Zhang 2005, p. 299.
  4. ^ Hulgan 2009, p. 2018-04-02 121 2.
  5. ^ Xulgan 2009, p. 2018-04-02 121 2.
  6. ^ Chen 2008 yil.
  7. ^ Jang 2005 yil.
  8. ^ Huang2012
  9. ^ Papaioannou 2014 yil

Adabiyotlar

  • Chjan, Chjun-fu; Chen, Syan-en; Li, Jingven; Yao, Bing; Lu, Xinzhon; Vang, Tszianfang (2005). "Grafiklarning qo'shni vertex bilan ajralib turadigan umumiy ranglari to'g'risida". Fan Xitoy matematikasi. 48 (3): 289–299. doi:10.1360 / 03ys0207.
  • Xulgan, Jonathan (2009). "Qo'shni vertexni ajratib turadigan umumiy ranglarning qisqa dalillari". Diskret matematika. 309 (8): 2548–2550. doi:10.1016 / j.disc.2008.06.002.
  • Chen, Xiang'en (2008). "Delta = 3 bilan grafiklarning umumiy rang berish raqamlarini ajratib turuvchi tepada". Diskret matematika. 308 (17): 4003–4007. doi:10.1016 / j.disc.2007.07.091.
  • Xuang, D .; Vang, V.; Yan, C. (2012). "Grafiklarning umumiy xromatik sonini ajratib turuvchi tepalikdagi yozuv". Diskret matematika. 312 (24): 3544–3546. doi:10.1016 / j.disc.2012.08.006.
  • Chen, Meyron; Guo, Xiaofeng (2009). "Giperkubiklarning vertikalni ajratib turuvchi qirrasi va umumiy xromatik sonlari". Axborotni qayta ishlash xatlari. 109 (12): 599–602. doi:10.1016 / j.ipl.2009.02.006.
  • Vang, Yiqiao; Vang, Veyfan (2010). "Tashqi planar grafikalarning umumiy ranglarini ajratib turuvchi qo'shni tepalik". Kombinatorial optimallashtirish jurnali. 19 (2): 123–133. doi:10.1007 / s10878-008-9165-x.
  • P. de Mello, Seliya; Pedrotti, Vagner (2010). "Qarama-qarshi vertexni ajratib turuvchi befarqlik grafikalarining umumiy ranglanishi" (PDF). Matematika Contemporanea. 39: 101–110.[doimiy o'lik havola ]
  • Vang, Veyfan; Xuang, Danjun (2012). "Planar grafikalarning umumiy rangini ajratib turuvchi qo'shni tepalik". Kombinatorial optimallashtirish jurnali. 27 (2): 379. doi:10.1007 / s10878-012-9527-2.
  • Chen, Syan-en; Chjan, Chjun-fu (2008). "Maksimal darajasi kamida 6 ga teng bo'lgan umumlashtirilgan Halin grafikalarining AVDTC raqamlari". Acta Mathematicae Applicationsatae Sinica. 24 (1): 55–58. doi:10.1007 / s10878-012-9527-2.
  • Xuan, Dancun; Vang, Veyfan; Yan, Chengchao (2012). "Grafiklarning umumiy xromatik sonini ajratib turuvchi vertexdagi yozuv". Diskret matematika. 312 (24): 3544–3546. doi:10.1016 / j.disc.2012.08.006.
  • Papaioannou, A .; Raftopoulou, C. (2014). "4 muntazam grafiklarning AVDTC-da". Diskret matematika. 330: 20–40. doi:10.1016 / j.disc.2014.03.019.
  • Luiz, Atilio G.; Campos, CN .; de Mello, KP (2015). "AVD - to'liq ekvartartitli grafikalarning umumiy ranglanishi". Diskret amaliy matematika. 184: 189. doi:10.1016 / j.dam.2014.11.006.