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"”.

  1. 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 …

    vcu Repository record for Graph Coloring Reconfiguration (opens in a new tab)

  2. 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 …

    wvu Repository record for Graph coloring and flows (opens in a new tab)

  3. 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 …

    texas-state Repository record for Efficient Vertex-Centric Graph Coloring (opens in a new tab)

  4. 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 …

    rice Repository record for Register allocation via graph coloring (opens in a new tab)

  5. 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 …

    vcu Repository record for Selected Problems in Graph Coloring (opens in a new tab)

  6. 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 …

    texas-state Repository record for Out-of-Core Graph Coloring Algorithm (opens in a new tab)

  7. 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} …

    wvu Repository record for From Graph Coloring to Receptor Clustering (opens in a new tab)

  8. 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 …

    wvu Repository record for Graph Coloring Problems and Group Connectivity (opens in a new tab)

  9. 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} …

    wvu Repository record for From Graph Coloring to Receptor Clustering (opens in a new tab)

  10. 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 …

    must-thes Repository record for Graph coloring algorithms on random graphs (opens in a new tab)

  11. 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 …

    rice Repository record for Graph Coloring, Zero Forcing, and Related Problems (opens in a new tab)

  12. 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 …

    ku Repository record for Polynomials associated with graph coloring and orientations (opens in a new tab)

  13. 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 .

    uiuc Repository record for Problems in Graph Coloring and Graph Structure (opens in a new tab)

  14. 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 …

    lethbridge Repository record for Graph coloring in sparse derivative matrix computation (opens in a new tab)

  15. 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 …

    wvu Repository record for A Study on Graph Coloring and Digraph Connectivity (opens in a new tab)

  16. 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 …

    nps Repository record for A graph coloring algorithm and a scheduling problem (opens in a new tab)

  17. 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 …

    gatech Repository record for On probabilistic, planar, and descriptive graph coloring problems (opens in a new tab)

  18. 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 …

    cornell Repository record for On Graph Coloring, Max Cut, and Semidefinite Rank (opens in a new tab)

Page 1 of 10