Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Тотальне розфарбування в теорії графів — це спосіб розфарбування вершин і (ребер) графа. В загальному випадку, якщо не сказано іншого, забарвлення завжди вважається правильним в тому сенсі, що немає суміжних ребер та вершин на кінцях ребер, які розфарбовані в один і той же колір. Тотальне хроматичне число χ″(G) графа G — це найменше число кольорів, необхідних для тотального розфарбування G.
Тотальним графом T = T(G) графа G називається граф, в якому
- множина вершин графа T відповідає вершинам і ребрам графа G;
- дві вершини T суміжні тоді і тільки тоді, коли відповідні елементи в G або суміжні, або інцидентні.
При такому визначенні тотальне розфарбування стає (правильним) вершинним розфарбуванням тотального графа.
Деякі властивості χ″(G):
- χ″(G) ≥ Δ(G) + 1.
- χ″(G) ≤ Δ(G) + 1026. (Molloy, Reed, 1998)
- χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) для досить великого Δ(G). (Hind, Molloy, Reed, 1998)
- χ″(G) ≤ ch′(G) + 2.
Δ(G) — це максимальний степінь, а ch′(G) — [en].
Тотальне розфарбування виникає природним шляхом, оскільки це просто суміш розфарбування вершин і ребер. Наступний крок — це розгляд верхніх меж тотального хроматичного числа в термінах максимальної степені за аналогією теорем Брукса або Візінга. Виявилося, що визначення верхніх меж тотальної розмальовки як функції від максимального степеня є складним завданням, яке залишається нерозв'язаним понад 40 років. Найбільш відома здогадка має такий вигляд.
Гіпотеза про тотальну розмальовку. ([en], Візинг)
- χ″(G) ≤ Δ(G) + 2.
Очевидно, термін «тотальне розфарбування» і формулювання гіпотези, незалежно один від одного, запропонували [en] і Візінг у численних публікаціях між 1964 і 1968 роками. (Дивись книгу Йонсена та Тофта (Jensen, Toft, 1995) для деталей.)
Відомо, що гіпотеза справедлива для декількох важливих класів графів, таких як двочасткові графи і більшість планарних графів, за винятком графів з максимальним степенем 6. Випадок планарних графів буде розв'язано, якщо буде доведено, що [en] про планарні графи правильна. Також, якщо [en] справедлива, то χ″(G) ≤ Δ(G) + 3.
Відомі деякі результати пов'язані з тотальним розфарбуванням. Наприклад, Кілакос і Рід (Kirakos, Reed, 1993) довели, що дробовий хроматичний індекс тотального графа для графа G не перевершує Δ(G) + 2.
Існує зв'язок між реберним графом і тотальним графом: T(G) є ейлеровим тоді і тільки тоді, коли L(G) ейлерів.
Див. також
Посилання
- Hind, Hugh; Molloy, Michael; (1998). Total coloring with Δ + poly(logΔ) colors. . 28 (3): 816—821. doi:10.1137/S0097539795294578.
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. .
- Kilakos, Kyriakos; (1993). Fractionally colouring total graphs. Combinatorica. 13 (4): 435—440. doi:10.1007/BF01303515.
- Molloy, Michael; (1998). A bound on the total chromatic number. Combinatorica. 18 (2): 241—280. doi:10.1007/PL00009820.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z povnim rozfarbuvannyam Totalne rozfarbuvannya v teoriyi grafiv ce sposib rozfarbuvannya vershin i reber grafa V zagalnomu vipadku yaksho ne skazano inshogo zabarvlennya zavzhdi vvazhayetsya pravilnim v tomu sensi sho nemaye sumizhnih reber ta vershin na kincyah reber yaki rozfarbovani v odin i toj zhe kolir Totalne hromatichne chislo x G grafa G ce najmenshe chislo koloriv neobhidnih dlya totalnogo rozfarbuvannya G Pravilne totalne rozfarbuvannya klitki Fostera shistma kolorami Totalne hromatichne chislo cogo grafa dorivnyuye 6 oskilki stepin kozhnoyi vershini dorivnyuye 5 5 sumizhnih reber 1 vershina 6 Totalnim grafom T T G grafa G nazivayetsya graf v yakomu mnozhina vershin grafa T vidpovidaye vershinam i rebram grafa G dvi vershini T sumizhni todi i tilki todi koli vidpovidni elementi v G abo sumizhni abo incidentni Pri takomu viznachenni totalne rozfarbuvannya staye pravilnim vershinnim rozfarbuvannyam totalnogo grafa Deyaki vlastivosti x G x G D G 1 x G D G 1026 Molloy Reed 1998 x G D G 8 ln8 D G dlya dosit velikogo D G Hind Molloy Reed 1998 x G ch G 2 D G ce maksimalnij stepin a ch G en Totalne rozfarbuvannya vinikaye prirodnim shlyahom oskilki ce prosto sumish rozfarbuvannya vershin i reber Nastupnij krok ce rozglyad verhnih mezh totalnogo hromatichnogo chisla v terminah maksimalnoyi stepeni za analogiyeyu teorem Bruksa abo Vizinga Viyavilosya sho viznachennya verhnih mezh totalnoyi rozmalovki yak funkciyi vid maksimalnogo stepenya ye skladnim zavdannyam yake zalishayetsya nerozv yazanim ponad 40 rokiv Najbilsh vidoma zdogadka maye takij viglyad Gipoteza pro totalnu rozmalovku en Vizing x G D G 2 Ochevidno termin totalne rozfarbuvannya i formulyuvannya gipotezi nezalezhno odin vid odnogo zaproponuvali en i Vizing u chislennih publikaciyah mizh 1964 i 1968 rokami Divis knigu Jonsena ta Tofta Jensen Toft 1995 dlya detalej Vidomo sho gipoteza spravedliva dlya dekilkoh vazhlivih klasiv grafiv takih yak dvochastkovi grafi i bilshist planarnih grafiv za vinyatkom grafiv z maksimalnim stepenem 6 Vipadok planarnih grafiv bude rozv yazano yaksho bude dovedeno sho en pro planarni grafi pravilna Takozh yaksho en spravedliva to x G D G 3 Vidomi deyaki rezultati pov yazani z totalnim rozfarbuvannyam Napriklad Kilakos i Rid Kirakos Reed 1993 doveli sho drobovij hromatichnij indeks totalnogo grafa dlya grafa G ne perevershuye D G 2 Isnuye zv yazok mizh rebernim grafom i totalnim grafom T G ye ejlerovim todi i tilki todi koli L G ejleriv Div takozhPovne rozfarbuvannyaPosilannyaHind Hugh Molloy Michael 1998 Total coloring with D poly logD colors 28 3 816 821 doi 10 1137 S0097539795294578 Jensen Tommy R Toft Bjarne 1995 Graph coloring problems New York Wiley Interscience ISBN 0 471 02865 7 Kilakos Kyriakos 1993 Fractionally colouring total graphs Combinatorica 13 4 435 440 doi 10 1007 BF01303515 Molloy Michael 1998 A bound on the total chromatic number Combinatorica 18 2 241 280 doi 10 1007 PL00009820