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 763 for “"coloring"”.
-
Intersperse Coloring
In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter …
-
Coloring Problems
This thesis considers several coloring problems all of which have a combinatorial flavor. We review some results on the chromatic number of the plane, and improve a bound on the value of regressive Ramsey numbers. The main work of this thesis considers the problem of whether given any n ≥ 1; one …
-
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 …
-
Graph Coloring Reconfiguration
… such as mathematics and computer science.The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type of Kempe swap. An α, β-Kempe swap in a properly colored graph interchanges the …
-
Coloring clique hypergraphs
… a set of k colors. A map c : V Sk is a proper k-coloring for CH(G) if any maximal clique of G with at least two vertices receives at least two distinct colors. Let W ⊂ V, and let s ≥ 1. We say that G is (W, s)-extendible if any assignment on W with at most s colors can be extended to a proper …
-
Graph coloring and flows
… by using a technical lemma.;Part 2. A star coloring of an undirected graph G is a proper vertex coloring of G such that any path of length 3 in G is not bi-colored. The star chromatic number of a family of graphs G , denoted by chis( G ), is the minimum number of colors that are necessary to …
-
Dynamic coloring of graphs
… we introduce and study the idea of a dynamic coloring of a graph, a coloring in which any multiple-degree vertex of the graph must be adjacent to at least two color classes.;As parts of the overall research, we study (for some interesting subjects of colorings) the corresponding subjects of …
-
Edge coloring of simple graphs and edge -face coloring of simple plane graphs
… a simple plane graph G, an edge-face k-coloring of G is a function &phis; : E(G) ∪ F(G) {lcub}1, ···, k{rcub} such that, for any two adjacent elements a, b ∈ E(G) ∪ F(G), &phis;( a) ≠ &phis;(b). Denote chie( G), chief(G), Delta( G) the edge chromatic number, the edge-face chromatic …
-
Efficient Vertex-Centric Graph Coloring
Graph coloring is a way of labeling (with labels traditionally referred to as “colors”) the elements of a graph with the constraint that no two adjacent vertices have the same color and that as few colors should be used as possible. In addition to many theoretical problems, graph coloring lends …
-
Coloring Graphs with Forbidden Minors
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t − 1)-colorable. This conjecture has been proved true for t ≤ 6, but remains …
-
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 …
-
Register allocation via graph coloring
… first global register allocator based on graph coloring. This thesis describes a series of improvements and extensions to the Yorktown allocator. There are four primary results: (1) Optimistic coloring. Chaitin's coloring heuristic pessimistically assumes any node of high degree will not be …
-
Selected Problems in Graph Coloring
… K1 ∨P4. For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a function f : V (G) → [k] such that |f(v) ∩f (w)| < d(v,w) for all distinct v, w ∈ V(G). The t-tone chromatic number of G, denoted τt(G), is the minimum k such that G is t-tone k-colorable. For small values of t, we prove sharp or …
-
Hall's condition and list coloring.
… V(G){dollar} then G has a proper vertex coloring {dollar}\\phi{dollar} with {dollar}\\phi(v)\\in L(v)\\ (\\forall v\\in V(G)).{dollar} The Hall number h(G) is defined like the choice number is defined, except that an extra non-triviality condition, called Hall's condition, must be …
-
On Some Hypergraph Coloring Algorithms
Of a given bipartite graph G = (V, E), it is elementary to construct a bipartition in timeO(|V |+|E|). For a given k-graph H = H(k) with k ≥ 3 fixed, Lovász proved that deciding whether H is bipartite is NP-complete. In this thesis, we consider the average running time of this problem. For that, …
Page 1 of 39