Důkaz Goldberg-Seymourovy domněnky s pomocí počítače
| školitel: | Mgr. Jan Volec, Ph.D. |
| e-mail: | zobrazit e-mail |
| typ práce: | |
| zaměření: | MINF, APIN |
| klíčová slova: | Teorie grafů, hranová barevnost, párování, počítačově asistované důkazy |
| odkaz: | http://honza.ucw.cz/thesis |
| popis: | Tématem této práce je jeden z nejznámějších problémů z oblasti hránové barevnosti grafů, kde je cílem pokrýt množinu hran grafu co nejmenším počtem párování. Jinými slovy, chceme všem hranám přiřadit barvy tak, aby každé dvě sousední hrany dostaly různou barvu. Goldberg-Seymourova domněnka o hranové barevnosti multigrafů říká, že libovolný multigraf jehož každý vrchol má stupeň nejvýše D lze hranově obarvit pomocí max(D+1, w) barev, kde w značí nejmenší přirozené číslo takové, že pro všechny H podgrafy G s lichým počtem vrcholů číslo w shora odhaduje zlomek 2|E(H)|/(|V(H)|-1). Číslo w je zajisté dolním odhadem, a stejně tak je dolním odhadem i číslo D. Přestože Petersenův graf má D=3 i w=3, je známo, že není hranově-3-obarvitelný, a proto je max(D+1,w) nejlepší horní odhad, v jaký lze doufat. Cílem této práce je nastudovat nedávný důkaz Goldberg-Seymourovy domněnky a případně též navrhnout verifikaci pomocných tvrzení v tomto důkazu pomocí počítače. |
| literatura: | A. Bondy, U.S.R. Murty: Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008 G. Chen, G. Jing, W. Zang: Proof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs, https://arxiv.org/abs/1901.10316 https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture |
| naposledy změněno: | 02.08.2024 04:52:13 |
za obsah této stránky zodpovídá:
Ľubomíra Dvořáková | naposledy změněno: 12.9.2011