Please use this identifier to cite or link to this item:
Title: Woodall's conjecture and the Lucchesi-Younger theorem
Author: Moles Gené, Oriol
Director/Tutor: Knauer, Kolja
Keywords: Teoria de grafs
Treballs de fi de grau
Anàlisi combinatòria
Graph theory
Bachelor's theses
Combinatorial analysis
Issue Date: 24-Jan-2022
Abstract: [en] This project is about directed cuts, directed joins and their packings. We study the open problem of Woodall’s Conjecture, a problem studied by many authors to such an extent that it even has a $5000 dollars prize for his demonstration set by G. Cornuéjols. We will also cover the Lucchesi-Younger Theorem proof which can be seen as a dual result of the conjecture and the counterexample for the Edmonds-Giles Conjecture, the weighted version of Woodall’s Conjecture. Besides studying the theory we have set ourselves the goal of proposing a program that given a graph, checks if all of its orientations validate the Woodall’s Conjecture. This program should be able to prove the conjecture, up to a certain number of vertices, by testing all the different combinations.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2022, Director: Kolja Knauer
Appears in Collections:Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
tfg_moles_gene_oriol.pdfMemòria1.25 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons