Vecchi, Davide
(2022)
Tutte's 5-flow conjecture.
[Laurea magistrale], Università di Bologna, Corso di Studio in
Matematica [LM-DM270]
Documenti full-text disponibili:
![[img]](http://amslaurea.unibo.it/style/images/fileicons/application_pdf.png) |
Documento PDF (Thesis)
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato
Download (563kB)
|
Abstract
The aim of this thesis is to show and put together the results, obtained so far, useful to tackle a conjecture of graph theory proposed in 1954 by William Thomas Tutte.
The conjecture in question is Tutte's 5-flow conjecture, which states that every bridgeless graph admits a nowhere-zero 5-flow, namely a flow with non-zero integer values between -4 and 4.
We will start by giving some basics on graph theory, useful for the followings, and proving some results about flows on oriented graphs and in particular about the flow polynomial.
Next we will treat two cases: graphs embeddable in the plane $\mathbb{R}^2$ and graphs embeddable in the projective plane $\mathbb{P}^2$.
In the first case we will see the correlation between flows and colorings and prove a theorem even stronger than Tutte's conjecture, using the 4-color theorem.
In the second case we will see how in 1984 Richard Steinberg used Fleischner's Splitting Lemma to show that there can be no minimal counterexample of the conjecture in the case of graphs in the projective plane.
In the fourth chapter we will look at the theorems of François Jaeger (1976) and Paul D. Seymour (1981). The former proved that every bridgeless graph admits a nowhere-zero 8-flow, the latter managed to go even further showing that every bridgeless graph admits a nowhere-zero 6-flow.
In the fifth and final chapter there will be a short introduction to the Tutte polynomial and it will be shown how it is related to the flow polynomial via the Recipe Theorem.
Finally we will see some applications of flows through the study of networks and their properties.
Abstract
The aim of this thesis is to show and put together the results, obtained so far, useful to tackle a conjecture of graph theory proposed in 1954 by William Thomas Tutte.
The conjecture in question is Tutte's 5-flow conjecture, which states that every bridgeless graph admits a nowhere-zero 5-flow, namely a flow with non-zero integer values between -4 and 4.
We will start by giving some basics on graph theory, useful for the followings, and proving some results about flows on oriented graphs and in particular about the flow polynomial.
Next we will treat two cases: graphs embeddable in the plane $\mathbb{R}^2$ and graphs embeddable in the projective plane $\mathbb{P}^2$.
In the first case we will see the correlation between flows and colorings and prove a theorem even stronger than Tutte's conjecture, using the 4-color theorem.
In the second case we will see how in 1984 Richard Steinberg used Fleischner's Splitting Lemma to show that there can be no minimal counterexample of the conjecture in the case of graphs in the projective plane.
In the fourth chapter we will look at the theorems of François Jaeger (1976) and Paul D. Seymour (1981). The former proved that every bridgeless graph admits a nowhere-zero 8-flow, the latter managed to go even further showing that every bridgeless graph admits a nowhere-zero 6-flow.
In the fifth and final chapter there will be a short introduction to the Tutte polynomial and it will be shown how it is related to the flow polynomial via the Recipe Theorem.
Finally we will see some applications of flows through the study of networks and their properties.
Tipologia del documento
Tesi di laurea
(Laurea magistrale)
Autore della tesi
Vecchi, Davide
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum A: Generale e applicativo
Ordinamento Cds
DM270
Parole chiave
Tutte nowhere-zero k-flow graph coloring
Data di discussione della Tesi
25 Marzo 2022
URI
Altri metadati
Tipologia del documento
Tesi di laurea
(NON SPECIFICATO)
Autore della tesi
Vecchi, Davide
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum A: Generale e applicativo
Ordinamento Cds
DM270
Parole chiave
Tutte nowhere-zero k-flow graph coloring
Data di discussione della Tesi
25 Marzo 2022
URI
Statistica sui download
Gestione del documento: