Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Однозна чно розфарбо вуваний граф це k колірний граф що допускає тільки одне правильне k розфарбування з точністю до пер

Однозначно розфарбовуваний граф

Однозначно розфарбовуваний граф

Однозна́чно розфарбо́вуваний граф — це k-колірний граф, що допускає тільки одне (правильне) k-розфарбування (з точністю до перестановки кольорів).

Приклади

Повний граф є однозначно розфарбовуваним, оскільки існує лише одне допустиме розфарбування — кожній вершині призначається свій колір.

Будь-яке k-дерево однозначно розфарбовується в (k + 1) колір. Однозначно розфарбовуються в 4 кольори планарні графи — це точно графи Аполлонія, тобто планарні 3-дерева.

Властивості

Деякі властивості однозначно k-розфарбовуваного графа G з n вершинами і m ребрами:

  1. m ≥ (k — 1) n — k (k -1)/2

Пов'язані концепції

Мінімальна недосконалість

Мінімально недосконалий граф — це граф, e якому будь-який підграф є досконалим. Видалення будь-якої вершини з мінімально недосконалого графа залишає однозначно розфарбовуваний підграф.

Однозначне розфарбування ребер

image
Однозначне 3-розфарбування ребер узагальненого графа Петерсена G(9,2)

Однозначно реберно-розфарбовуваний граф — це реберно k-колірний граф, що допускає тільки одне (правильне) реберне k-розфарбування з точністю до перестановки кольорів. Тільки шляхи та цикли допускають однозначне реберне 2-розфарбування. Для будь-якого значення k зірки K1,k є однозначно реберно k-розфарбовуваними графами. Проте Вільсон висловив гіпотезу, а Томасон довів, що за k ≥ 4 це єдині члени цього сімейства. Існують, однак, однозначно реберно 3-розфарбовувані графи, що не потрапляють до цієї класифікації, як, наприклад, граф трикутної піраміди.

Якщо кубічний граф однозначно реберно 3-розфарбовуваний, він повинен мати рівно три гамільтонових цикли, утворених ребрами двох (з трьох) кольорів, однак деякі кубічні графи тільки з трьома гамільтоновими циклами однозначного реберного 3-розфарбування не мають . Будь-який простий планарний кубічний граф, що допускає єдине реберне 3-розфарбування, містить трикутник, але Тат зауважив, що узагальнений граф Петерсена G(9,2) є непланарним графом без трикутників, однак він однозначно реберно 3-розфарбовуваний. Багато років цей граф був єдиним прикладом таких графів (див. статті Болобаша і Швенка), але тепер відомо нескінченно багато непланарних кубічних графів без трикутників, які мають однозначне реберне 3-розфарбування.

Однозначне тотальне розфарбування

Однозначно тотально розфарбовуваний граф — це тотально k-колірний граф, що допускає тільки одне (правильне) тотальне k-розфарбування (з точністю до перестановки кольорів).

[en], шляхи й цикли з довжиною, що ділиться на 3, є однозначно тотально розфарбовуваними графами. Махмудіан і Шокроллахі висунули гіпотезу, что тільки ці графи й утворюють сімейство.

Деякі властивості однозначно тотально k-розфарбовуваного графа G з n вершинами:

  1. χ″(G) = Δ(G) + 1, крім випадку G = K2.
  2. Δ(G) ≤ 2 δ(G).
  3. Δ(G) ≤ n/2 + 1.

Тут χ″(G) — тотальне хроматичне число; Δ(G) — найбільший степінь, а δ(G) — найменший степінь.

Примітки

  1. Fowler, 1998.
  2. Truszczyński, 1984.
  3. Xu, 1990.
  4. Wilson, 1976.
  5. Thomason, 1978.
  6. Belcastro, Haas, 2015.
  7. Tutte, 1976.
  8. Bollobás, 1978.
  9. Schwenk, 1989.
  10. Mahmoodian, Shokrollahi, 1995.
  11. Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997.
  12. Akbari, 2003.

Література

  • S. Akbari. Two conjectures on uniquely totally colorable graphs // . — 2003. — Т. 266, вип. 1-3. — С. 41–45. — DOI:10.1016/S0012-365X(02)00797-5.
  • S. Akbari, M. Behzad, H. Hajiabolhassan, E. S. Mahmoodian. Uniquely total colorable graphs // . — 1997. — Т. 13, вип. 4. — С. 305–314. — DOI:10.1016/S0012-365X(02)00797-5.
  • Sarah-Marie Belcastro, Ruth Haas. Triangle-free uniquely 3-edge colorable cubic graphs // Contributions to Discrete Mathematics. — 2015. — Т. 10, вип. 2. — С. 39–44. — arXiv:1508.06934.
  • Béla Bollobás. Extremal Graph Theory. — Academic Press, 1978. — Т. 11. — (LMS Monographs)
  • Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)
  • Christopher J. Hillar, Troels Windfeldt. Algebraic characterization of uniquely vertex colorable graphs // . — 2008. — Т. 98, вип. 2. — С. 400–414. — (Series B). — DOI:10.1016/j.jctb.2007.08.004.
  • E. S. Mahmoodian, M. A. Shokrollahi. Combinatorics Advances. — Dordrecht; Boston; London : Kluwer Academic Publishers, 1995. — Т. 329. — С. 321–324. — (Mathematics and its applications)
  • Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // . — 1989. — Т. 47, вип. 1. — С. 53–59. — DOI:10.1016/0095-8956(89)90064-6.
  • A. G. Thomason. Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). — 1978. — Т. 3. — С. 259–268. — (Annals of Discrete Mathematics)
  • M. Truszczyński. Finite and Infinite Sets. Vol. I, II. Proceedings of the sixth Hungarian combinatorial colloquium held in Eger, July 6–11, 1981 / András Hajnal, László Lovász, Vera T. Sós. — North-Holland, Amsterdam, 1984. — Т. 37. — С. 733–748. — (Colloq. Math. Soc. János Bolyai)
  • William T. Tutte. Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I. — Accad. Naz. Lincei, Rome, 1976. — С. 193–199. Atti dei Convegni Lincei, No. 17.. Як процитовано в Белкастро й Гааса (Belcastro, Haas, 2015).
  • Shao Ji Xu. The size of uniquely colorable graphs // . — 1990. — Т. 50, вип. 2. — С. 319–320. — (Series B). — DOI:10.1016/0095-8956(90)90086-F.
  • R. J. Wilson. Proc. British Comb. Conf. 1975. — Winnipeg : Utilitas Math, 1976. — С. 696.. Як процитовано в Томасона (Thomason, 1978).

Посилання

  • Weisstein, Eric W. Однозначно k-розфарбовуваний граф(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Odnozna chno rozfarbo vuvanij graf ce k kolirnij graf sho dopuskaye tilki odne pravilne k rozfarbuvannya z tochnistyu do perestanovki koloriv PrikladiPovnij graf ye odnoznachno rozfarbovuvanim oskilki isnuye lishe odne dopustime rozfarbuvannya kozhnij vershini priznachayetsya svij kolir Bud yake k derevo odnoznachno rozfarbovuyetsya v k 1 kolir Odnoznachno rozfarbovuyutsya v 4 kolori planarni grafi ce tochno grafi Apolloniya tobto planarni 3 dereva VlastivostiDeyaki vlastivosti odnoznachno k rozfarbovuvanogo grafa G z n vershinami i m rebrami m k 1 n k k 1 2Pov yazani koncepciyiMinimalna nedoskonalist Minimalno nedoskonalij graf ce graf e yakomu bud yakij pidgraf ye doskonalim Vidalennya bud yakoyi vershini z minimalno nedoskonalogo grafa zalishaye odnoznachno rozfarbovuvanij pidgraf Odnoznachne rozfarbuvannya reber Odnoznachne 3 rozfarbuvannya reber uzagalnenogo grafa Petersena G 9 2 Odnoznachno reberno rozfarbovuvanij graf ce reberno k kolirnij graf sho dopuskaye tilki odne pravilne reberne k rozfarbuvannya z tochnistyu do perestanovki koloriv Tilki shlyahi ta cikli dopuskayut odnoznachne reberne 2 rozfarbuvannya Dlya bud yakogo znachennya k zirki K1 k ye odnoznachno reberno k rozfarbovuvanimi grafami Prote Vilson visloviv gipotezu a Tomason doviv sho za k 4 ce yedini chleni cogo simejstva Isnuyut odnak odnoznachno reberno 3 rozfarbovuvani grafi sho ne potraplyayut do ciyeyi klasifikaciyi yak napriklad graf trikutnoyi piramidi Yaksho kubichnij graf odnoznachno reberno 3 rozfarbovuvanij vin povinen mati rivno tri gamiltonovih cikli utvorenih rebrami dvoh z troh koloriv odnak deyaki kubichni grafi tilki z troma gamiltonovimi ciklami odnoznachnogo rebernogo 3 rozfarbuvannya ne mayut Bud yakij prostij planarnij kubichnij graf sho dopuskaye yedine reberne 3 rozfarbuvannya mistit trikutnik ale Tat zauvazhiv sho uzagalnenij graf Petersena G 9 2 ye neplanarnim grafom bez trikutnikiv odnak vin odnoznachno reberno 3 rozfarbovuvanij Bagato rokiv cej graf buv yedinim prikladom takih grafiv div statti Bolobasha i Shvenka ale teper vidomo neskinchenno bagato neplanarnih kubichnih grafiv bez trikutnikiv yaki mayut odnoznachne reberne 3 rozfarbuvannya Odnoznachne totalne rozfarbuvannya Odnoznachno totalno rozfarbovuvanij graf ce totalno k kolirnij graf sho dopuskaye tilki odne pravilne totalne k rozfarbuvannya z tochnistyu do perestanovki koloriv en shlyahi j cikli z dovzhinoyu sho dilitsya na 3 ye odnoznachno totalno rozfarbovuvanimi grafami Mahmudian i Shokrollahi visunuli gipotezu chto tilki ci grafi j utvoryuyut simejstvo Deyaki vlastivosti odnoznachno totalno k rozfarbovuvanogo grafa G z n vershinami x G D G 1 krim vipadku G K2 D G 2 d G D G n 2 1 Tut x G totalne hromatichne chislo D G najbilshij stepin a d G najmenshij stepin PrimitkiFowler 1998 Truszczynski 1984 Xu 1990 Wilson 1976 Thomason 1978 Belcastro Haas 2015 Tutte 1976 Bollobas 1978 Schwenk 1989 Mahmoodian Shokrollahi 1995 Akbari Behzad Hajiabolhassan Mahmoodian 1997 Akbari 2003 LiteraturaS Akbari Two conjectures on uniquely totally colorable graphs 2003 T 266 vip 1 3 S 41 45 DOI 10 1016 S0012 365X 02 00797 5 S Akbari M Behzad H Hajiabolhassan E S Mahmoodian Uniquely total colorable graphs 1997 T 13 vip 4 S 305 314 DOI 10 1016 S0012 365X 02 00797 5 Sarah Marie Belcastro Ruth Haas Triangle free uniquely 3 edge colorable cubic graphs Contributions to Discrete Mathematics 2015 T 10 vip 2 S 39 44 arXiv 1508 06934 Bela Bollobas Extremal Graph Theory Academic Press 1978 T 11 LMS Monographs Thomas Fowler Unique Coloring of Planar Graphs Georgia Institute of Technology Mathematics Department 1998 Ph D thesis Christopher J Hillar Troels Windfeldt Algebraic characterization of uniquely vertex colorable graphs 2008 T 98 vip 2 S 400 414 Series B DOI 10 1016 j jctb 2007 08 004 E S Mahmoodian M A Shokrollahi Combinatorics Advances Dordrecht Boston London Kluwer Academic Publishers 1995 T 329 S 321 324 Mathematics and its applications Allen J Schwenk Enumeration of Hamiltonian cycles in certain generalized Petersen graphs 1989 T 47 vip 1 S 53 59 DOI 10 1016 0095 8956 89 90064 6 A G Thomason Advances in Graph Theory Cambridge Combinatorial Conf Trinity College Cambridge 1977 1978 T 3 S 259 268 Annals of Discrete Mathematics M Truszczynski Finite and Infinite Sets Vol I II Proceedings of the sixth Hungarian combinatorial colloquium held in Eger July 6 11 1981 Andras Hajnal Laszlo Lovasz Vera T Sos North Holland Amsterdam 1984 T 37 S 733 748 Colloq Math Soc Janos Bolyai William T Tutte Colloquio Internazionale sulle Teorie Combinatorie Rome 1973 Tomo I Accad Naz Lincei Rome 1976 S 193 199 Atti dei Convegni Lincei No 17 Yak procitovano v Belkastro j Gaasa Belcastro Haas 2015 Shao Ji Xu The size of uniquely colorable graphs 1990 T 50 vip 2 S 319 320 Series B DOI 10 1016 0095 8956 90 90086 F R J Wilson Proc British Comb Conf 1975 Winnipeg Utilitas Math 1976 S 696 Yak procitovano v Tomasona Thomason 1978 PosilannyaWeisstein Eric W Odnoznachno k rozfarbovuvanij graf angl na sajti Wolfram MathWorld

Дата публікації:
Топ