|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (advisor) ; Sereni, Jean Sébastien (referee) ; Fiala, Jiří (referee)
In this thesis we consider four different problems in structural graph theory: We start studying the structure of graphs having a nowhere-zero 5-flow. We give a cha- racterization of the graphs that have a nowhere-zero 5-flow in terms of the existence of a (1, 2)-factor. For the second problem we introduce a new type of labeling of graphs that we call additive coloring. This coloring is a variation of the injective coloring. Indeed, it is an injective colo- ring with arithmetic restrictions determined by the graph. We study the properties and the structure of graphs admitting this type of labeling. Moreover, we study the computational complexity of the problem of computing this labeling for a graph with a fixed number of colors. In the third problem we study how the structure of caterpillars is encoded by the chromatic symmetric function or, equivalently, the U-polynomial. Stanley conjectured that the symme- tric chromatic polynomial distinguishes non-isomorphic trees. In this thesis we prove that the conjecture is true for proper caterpillars (caterpillars without vertices of degree 2). Finally, we study the structure of infinite graphs having a complete graph as a minor or as a topological minor. It is known that bounds on the degree of the vertices is not enough to ensure the existence of a complete...
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (advisor) ; Sereni, Jean Sébastien (referee) ; Fiala, Jiří (referee)
In this thesis we consider four different problems in structural graph theory: We start studying the structure of graphs having a nowhere-zero 5-flow. We give a cha- racterization of the graphs that have a nowhere-zero 5-flow in terms of the existence of a (1, 2)-factor. For the second problem we introduce a new type of labeling of graphs that we call additive coloring. This coloring is a variation of the injective coloring. Indeed, it is an injective colo- ring with arithmetic restrictions determined by the graph. We study the properties and the structure of graphs admitting this type of labeling. Moreover, we study the computational complexity of the problem of computing this labeling for a graph with a fixed number of colors. In the third problem we study how the structure of caterpillars is encoded by the chromatic symmetric function or, equivalently, the U-polynomial. Stanley conjectured that the symme- tric chromatic polynomial distinguishes non-isomorphic trees. In this thesis we prove that the conjecture is true for proper caterpillars (caterpillars without vertices of degree 2). Finally, we study the structure of infinite graphs having a complete graph as a minor or as a topological minor. It is known that bounds on the degree of the vertices is not enough to ensure the existence of a complete...
|
guest ::
RSS feed.