We consider edge-colorings and flows problems in Graph Theory that are hard to solve for Class 2 graphs. Most of them are strongly related to some outstanding open conjectures, such as the Cycle Double Cover Conjecture, the Berge-Fulkerson Conjecture, the Petersen Coloring Conjecture and the Tutte's 5-flow Conjecture. We obtain some new restrictions on the structure of a possible minimum counterexample to the former two conjectures. We prove that the Petersen graph is, in a specific sense, the only graph that could appear in the Petersen Coloring Conjecture, and we provide evidence that led to propose an analogous of the Tutte's 5-flow conjecture in higher dimensions. We prove a characterization result and a sufficient condition for general graphs in relation to another edge-coloring problem, which is the determination of the palette index of a graph.
| Identifer | oai:union.ndltd.org:unitn.it/oai:iris.unitn.it:11572/406620 |
| Date | 18 April 2024 |
| Creators | Tabarelli, Gloria |
| Contributors | Tabarelli, Gloria |
| Publisher | Università degli studi di Trento, place:TRENTO |
| Source Sets | Università di Trento |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | firstpage:1, lastpage:125, numberofpages:125 |
Page generated in 0.0012 seconds