Experimentální ověření hypotézy o hranové vybíravosti

• Název práce v češtině: Experimentální ověření hypotézy o hranové vybíravosti
• Název v anglickém jazyce: Experimental evaluation of the edge choosability conjecture
• Akademický rok vypsání: 2023/2024
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 15.05.2023
• Datum zadání: 15.05.2023
• Datum potvrzení stud. oddělením: 24.05.2023

Zásady pro vypracování

Hypotéza o hranové vybíravosti říká, že hranová vybíravost každého grafu je rovná jeho hranové barevnosti. Tato hypotéza byla dokázána pro některé zajímavé třídy grafů (bipartitní grafy, rovinné grafy, ...). Cílem práce je využít metodu Alona a Tarsiho pro testování grafové vybíravosti k experimentálnímu ověření (nebo vyvrácení) této hypotézy, například na všech malých či náhodně generovaných grafech z omezených tříd, a případně její teoretický důkaz pro další speciální třídy grafů.

Seznam odborné literatury

Noga Alon and Michael Tarsi: Colorings and orientations of graphs. Combinatorica, 12(2):125-134, 1992.
Fred Galvin: The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63 (1995), 153–158.
Zdeněk Dvořák: An efficient implementation and a strengthening of Alon-Tarsi list coloring method, https://arxiv.org/abs/2301.06571