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 181 for “"graph coloring"”.
-
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 …
-
Graph coloring and flows
… Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, we verify the conjecture for some families of snarks (Goldberg snarks, flower snarks) by using a technical …
-
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 …
-
Register allocation via graph coloring
… the 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 …
-
Selected Problems in Graph Coloring
… Borodin–Kostochka Conjecture states that for a graph G, if ∆(G) ≥ 9 and ω(G) ≤ ∆(G) − 1, then χ(G) ≤ ∆(G) − 1. We prove the Borodin–Kostochka Conjecture for (P5, gem)-free graphs, i.e., graphs with no induced P5 and no induced K1 ∨P4. For a graph G and t, k ∈ Z+ at-tone k-coloring of G is a …
-
Out-of-Core Graph Coloring Algorithm
… thesis develops an out-of-core algorithm for graph coloring. It dynamically partitions the graph into subgraphs, processes them in sequence, and records the color information needed by later subgraphs in a dense format. The algorithm is guaranteed to produce the same coloring as the first-fit …
-
From Graph Coloring to Receptor Clustering
1. Hued colorings for planar graphs, graphs of higher genus and K4-minor free graphs.;For integers k, r > 0, a (k,r) -coloring of a graph G is a proper coloring of the vertices of G with k colors such that every vertex v of degree d(v) is adjacent to vertices with at least min{lcub}d(v) ,r{rcub} …
-
Graph Coloring Problems and Group Connectivity
… ≥ 2, there exists a finite family F = F(p, t) of graphs that do not have a mod (2p + 1)-orientation, such that every graph G with independence number at most t either admits a mod (2p+1)-orientation or is contractible to a member in F. In particular, the graph family F(p, 2) is determined, and our …
-
From Graph Coloring to Receptor Clustering
1. Hued colorings for planar graphs, graphs of higher genus and K4-minor free graphs.;For integers k, r > 0, a (k,r) -coloring of a graph G is a proper coloring of the vertices of G with k colors such that every vertex v of degree d(v) is adjacent to vertices with at least min{lcub}d(v) ,r{rcub} …
-
Graph coloring algorithms on random graphs
"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two …
-
Graph Coloring, Zero Forcing, and Related Problems
… problems related to classical and dynamic coloring of graphs, and enumeration of graph attributes. In the first part of the thesis, I present new efficient methods to compute the chromatic and flow polynomials of specific families of graphs. The chromatic and flow polynomials count the …
-
Polynomials associated with graph coloring and orientations
We study colorings and orientations of graphs in two related contexts. Firstly, we generalize Stanley's chromatic symmetric function using the k-balanced colorings of Pretzel to create a new graph invariant. We show that in fact this invariant is a quasisymmetric function which has a positive …
-
Problems in Graph Coloring and Graph Structure
… set in the plane, and let G be the intersection graph of F . We studied the chromatic number of the complement of G. We also studied the transversal number of F , where the transversal number is the minimum size of a set of points that intersects all convex sets in F .
-
Graph coloring in sparse derivative matrix computation
… of Jacobian matrices can be posed as a graph coloring problem. Unidirectional coloring by Coleman and More [9] and bidirectional coloring independently proposed by Hossain and Steihaug [23] and Coleman and Verma [12] are techniques that employ graph theoretic ideas. In this thesis we …
-
A Study on Graph Coloring and Digraph Connectivity
This dissertation focuses on coloring problems in graphs and connectivity problems in digraphs. We obtain the following advances in both directions.;1. Results in graph coloring. For integers k,r > 0, a (k,r)-coloring of a graph G is a proper coloring on the vertices of G with k colors such that …
-
A graph coloring algorithm and a scheduling problem
The graph coloring problem is defined, and its importance in several applications is noted. A new algorithm to color graphs is presented and tested against the Welch-Powell algorithm. Significantly better results are obtained on a sequence of three hundred randomly generated graphs. The new …
-
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 …
-
On Graph Coloring, Max Cut, and Semidefinite Rank
… on two of Karp's original NP-complete problems, graph coloring and max cut, both of which have established semidefinite programming relaxations. We introduce the use of semidefinite programming complementary slackness conditions to understand when an optimal solution to one of these SDP …
Page 1 of 10