Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 14 of 14 for “"Choosability"”.
-
Online choosability of graphs
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-09-29 without embargo terms
-
Edge-choosability of Planar Graphs
According to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without …
-
Defect-1 Choosability of Graphs on Surfaces
… is list colouring and its associated parameters: choosability and choice number. The main result of this thesis is to show that every graph G of Euler genus μ is ⌈2 + √(3μ + 3)⌉–choosable with defect 1 (equivalently, with clustering 2). Thus allowing any defect, even 1, reduces the choice number …
-
Thomassen’s 5-Choosability Theorem Extends to Many Faces
… Such a result is analogous to Thomassen’s 5-choosability proof where arbitrarily many faces, rather than just one face, are permitted to have 3-lists. This result can also be thought of as a stronger form of a conjecture of Albertson which was solved in 2012 and asked whether a planar graph …
-
5-Choosability of Planar-plus-two-edge Graphs
We prove that graphs that can be made planar by deleting two edges are 5-choosable. To arrive at this, first we prove an extension of a theorem of Thomassen. Second, we prove an extension of a theorem Postle and Thomas. The difference between our extensions and the theorems of Thomassen and of …
-
Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles
The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is …
-
Coloring problems in graph theory
… a new variation to list coloring which we call choosability with union separation: For a graph G, a list assignment L to the vertices of G is a (k,k+t)-list assignment if every vertex is assigned a list of size at least k and the union of the lists of each pair of adjacent vertices is at least …
-
Choice numbers for unions of graphs
… all positive values of k. New results on (a b)-choosability of planar graphs, bipartite graphs and Cartesian products of graphs are also presented.
-
Local Perspectives on Planar Colouring
… Postle, both of Thomassen's theorems on the 5-choosability of planar graphs and 3-choosability of planar graphs of girth at least five carry over to the correspondence colouring setting. In this thesis, we show that the family of graphs that are critical for 5-correspondence colouring as well …
-
Small cycle cover, group coloring with related problems
… of graphs.;The concept of list coloring, choosability and choice number was introduced by Erdos, Rubin and Taylor in 1979 and Vizing in 1976. Alon and Tarsi proved that every bipartite planar graph is 3-choosable. Thomassen showed that every planar graph is 5-choosable and that every …
-
Extremal problems on variations of graph colorings
… for a question by \v Skrekovski regarding choosability with separation for planar graphs, and we completely answer a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question …
-
5-list-coloring graphs on surfaces
Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. This thesis develops new techniques to prove general theorems for 5-list-coloring graphs embedded in a fixed surface. Indeed, a general …
-
List Coloring Some Classes of 1-Planar Graphs
In list coloring we are given a graph G and a list assignment for G which assigns to each vertex of G a list of possible colors. We wish to find a coloring of the vertices of G such that each vertex uses a color from its list and adjacent vertices are given different colors. In this thesis we study …
-
Extremal problems on counting combinatorial structures
The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field. The complete balanced bipartite graph on $n$ …