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

• Thesis title in Czech: Experimentální ověření hypotézy o hranové vybíravosti
• Thesis title in English: Experimental evaluation of the edge choosability conjecture
• Academic year of topic announcement: 2023/2024
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 15.05.2023
• Date of assignment: 15.05.2023
• Confirmed by Study dept. on: 24.05.2023

Guidelines

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ů.

References

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