Důkaz Goldberg-Seymourovy domněnky s pomocí počítače
| advisor: | Mgr. Jan Volec, Ph.D. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MINF, APIN |
| key words: | Teorie grafů, hranová barevnost, párování, počítačově asistované důkazy |
| link: | http://honza.ucw.cz/thesis |
| description: | 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. |
| references: | 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 |
| last update: | 22.06.2022 20:14:27 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011