'K_7- og K_{4,4}-minors i grafer'
Forfatter
Taagaard, Birgitte
Semester
4. semester
Uddannelse
Udgivelsesår
2005
Resumé
Denne afhandling undersøger Hadwigers formodning og den svage Hadwiger-formodning for k=7 med fokus på K7- og K4,4-minors i grafer. Vi viser en kanttærskel: enhver graf med n punkter og mindst 5n-14 kanter kan sammentrækkes til K7. Vi karakteriserer desuden de grafer med n punkter og præcis 5n-15 kanter, som ikke kan sammentrækkes til K7, og viser at de er isomorfe med K2,2,2,3 og MP2-cockader. Dernæst bevises, at enhver 4-sammenhængende graf med mindst 4n-7 kanter enten er K7 eller indeholder en K4,4-minor. Dette bruges til at etablere, at enhver 7-kromatisk graf enten har en K7-minor eller en K4,4-minor, i overensstemmelse med den svage Hadwiger-formodning for k=7. Endelig identificeres egenskaber ved grafer af typen E3+H, som er kant-maksimale uden K7-minor. Arbejdet bygger på strukturel grafteori, herunder sammentrækninger, sammenhæng og forbudte delgrafer.
This thesis investigates Hadwiger’s conjecture and the weak Hadwiger conjecture for k=7, focusing on K7 and K4,4 graph minors. It establishes an edge threshold: any graph on n vertices with at least 5n-14 edges can be contracted to K7. It further characterizes graphs on n vertices with exactly 5n-15 edges that are not contractible to K7, showing they are isomorphic to K2,2,2,3 and MP2-cockades. Next, it proves that any 4-connected graph with at least 4n-7 edges is either K7 or contains a K4,4 minor. Leveraging this, the thesis shows that every 7-chromatic graph has either a K7 minor or a K4,4 minor, aligning with the weak Hadwiger conjecture for k=7. Finally, it identifies properties of graphs of the form E3+H that are edge-maximal without a K7 minor. The approach uses structural graph theory, including contractions, connectivity, and forbidden subgraphs.
[Dette resumé er genereret med hjælp fra AI direkte fra projektet (PDF)]