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 20 of 27 for “"List Coloring"”.
-
List-coloring and sum-list-coloring problems on graphs
<p>Graph coloring is a well-known and well-studied area of graph theory that has many applications. In this dissertation, we look at two generalizations of graph coloring known as list-coloring and sum-list-coloring. In both of these types of colorings, one seeks to first assign palettes of colors …
-
Hall's condition and list coloring.
… each {dollar}v\\in V(G){dollar} let L(v) be a list assignment to G. The well-known choice number c(G) (or sometimes referred to as list chromatic number of G) is the least integer j such that if {dollar}\\vert L(v)\\vert\\ge j{dollar} for all {dollar}v\\in V(G){dollar} then G has a proper …
-
5-list-coloring graphs on surfaces
… 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 paradigm is established which improves a number of previous results while resolving several open …
-
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 …
-
Problems in list coloring, triangle covering, and pursuit-evasion games
Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-14T16:02:09Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 11 littletuza.tex: 12675 bytes, checksum: addf3766f19108432eeb6fc23765de37 (MD5) uiucthesis2009.cls: 17082 bytes, checksum: …
-
On List-Coloring and the Sum List Chromatic Number of Graphs.
… thesis explores several of the major results in list-coloring in an expository fashion. As a specialization of list coloring, the sum list chromatic number is explored in detail. Ultimately, the thesis is designed to motivate the discussion of coloring problems and, hopefully, interest the reader …
-
Equitable List Coloring, Induced Linear Forests, and Routing in Rooted Graphs
We explicitly characterize the family of networks for which such a protocol exists. This characterization is given in terms of forbidden rooted minors, which leads to a linear time recognition algorithm for this family of networks. We obtain a similar characterization for the family of networks in …
-
Heterogeneous Generalizations of Vertex Coloring
… in some heterogeneous generalizations of vertex coloring, i.e. generalizations in which the relationship between the colors of two adjacent vertices may differ throughout the graph. For the most part, the results are from group coloring, group list coloring, and DP coloring. The main results are …
-
Coloring problems in graph theory
<p>We consider two branches of coloring problems for graphs: list coloring and packing coloring. We introduce 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 …
-
Coloring and constructing (hyper)graphs with restrictions
… existence of graphs and hypergraphs with certain coloring properties and other structural properties. In Chapter 2 we consider color-critical graphs that are nearly bipartite and have few edges. We prove a conjecture of Chen, Erdős, Gyárfás, and Schelp concerning the minimum number of edges in a …
-
Small cycle cover, group coloring with related problems
… Linial, Payan and Tarsi introduced group coloring in 1992 and proved that the group chromatic number for every planar graph is at most 6. It is shown that the bound 6 can be decreased to 5. Jaeger, Linial, Payan and Tarsi also proved that the group chromatic number for every planar graph …
-
Extensions of Galvin's Theorem
We discuss problems in list coloring with an emphasis on techniques that utilize oriented graphs. Our central theme is Galvin's resolution of the Dinitz problem (Galvin. J. Comb. Theory, Ser. B 63(1), 1995, 153--158). We survey the related work of Alon and Tarsi (Combinatorica 12(2) 1992, 125--134) …
-
An Introduction to List Colorings of Graphs
… and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of …
-
Upper density problems in infinite Ramsey theory
… graphs, up to a factor of 2. We also study a list coloring variant of the same problem. We show that there exists a way of assigning a list of size two to every edge in the complete graph on N such that, in every list coloring, there are monochromatic paths with density arbitrarily close to 1.
-
Coloring problems in combinatorics and descriptive set theory
In this dissertation we study problems related to colorings of combinatorial structures both in the “classical” finite context and in the framework of descriptive set theory, with applications to topological dynamics and ergodic theory. This work consists of two parts, each of which is in turn …
-
Coloring the Square of Planar Graphs Without 4-Cycles or 5-Cycles
… about \frac{3}{2} \Delta colors for such a coloring. To prove a stronger upper bound, we consider only planar graphs that contain no 4-cycles and no 5-cycles (but which may contain 3-cycles). Zhu, Lu, Wang, and Chen showed that for a graph G in this class with \Delta \ge 9, we can color G^2 …
-
Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm
… most celebrated and influential results in graph coloring, such as Brooks' Theorem and Vizing's Theorem, relate a graph's chromatic number to its clique number or maximum degree. Currently, several of the most important and enticing open problems in coloring, such as Reed's $\omega, \Delta, \chi$ …
-
On probabilistic, planar, and descriptive graph coloring problems
We investigate graph coloring problems from the perspective of three different types of graphs: graphs with forbidden bipartite subgraphs; planar graphs; and Borel graphs that are line graphs. We start with studying graph with forbidden bipartite subgraphs. We say a graph is $F$-free if it contains …
-
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
-
Colorings and list colorings of graphs and hypergraphs
Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-04-04T13:50:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 3 thesis.tex: 208138 bytes, checksum: 3f2bbfe42b155982f3fe9f0f51b4e863 (MD5) config1.eps: 12369 bytes, checksum: …
Page 1 of 2