|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (advisor) ; Sereni, Jean-Sébastien (referee)
In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.
|
|
|
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...
|
|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (advisor) ; Sereni, Jean-Sébastien (referee)
In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.
|
guest ::
