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 32 for “"Vertex coloring"”.

  1. Heterogeneous Generalizations of Vertex Coloring

    … results 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 …

    wvu Repository record for Heterogeneous Generalizations of Vertex Coloring (opens in a new tab)

  2. Vertex coloring with forbidden subgraphs

    … A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely related to the characterization of the line graphs in terms of forbidden subgraphs. By using {\it clique-width} and {\it perfect graphs} theory, we show that …

    wilfrid-laurier Repository record for Vertex coloring with forbidden subgraphs (opens in a new tab) Download PDF for Vertex coloring with forbidden subgraphs (opens in a new tab)

  3. Graph Homomorphisms and Vector Colorings

    A graph vertex coloring is an assignment of labels, which are referred to as colors, such that no two adjacent vertices receive the same color. The vertex coloring problem is NP-Complete [8], and so no polynomial time algorithm is believed to exist. The notion of a graph vector coloring was …

    south-carolina Repository record for Graph Homomorphisms and Vector Colorings (opens in a new tab)

  4. Algorithms for weighted coloring problems

    In this thesis, we studied a generalization of vertex coloring problem (VCP). A classical VCP is an assignment of colors to the vertices of a given graph such that no two adjacent vertices receive the same color. The objective is to find a coloring with the minimum number of colors. In the first …

    lethbridge Repository record for Algorithms for weighted coloring problems (opens in a new tab)

  5. Some Optimally Adaptive Parallel Graph Algorithms on EREW PRAM Model

    … assignment problems, and approximate vertex coloring. For all but the last two problems, the input data structure is an unordered list of edges, and divide-and-conquer is the paradigm for designing algorithms. One of the algorithms to solve the assignment problem makes use of an …

    ucf Repository record for Some Optimally Adaptive Parallel Graph Algorithms on EREW PRAM Model (opens in a new tab)

  6. Forbidden subgraphs and 3-colorability

    Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such …

    gatech Repository record for Forbidden subgraphs and 3-colorability (opens in a new tab)

  7. Generalized Colorings of Graphs

    A graph coloring is an assignment of labels called “colors” to certain elements of a graph subject to certain constraints. The proper vertex coloring is the most common type of graph coloring, where each vertex of a graph is assigned one color such that no two adjacent vertices share the same …

    clemson Repository record for Generalized Colorings of Graphs (opens in a new tab)

  8. Graph Theory for the Secondary School Classroom.

    … developed four units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.

    etsu Repository record for Graph Theory for the Secondary School Classroom. (opens in a new tab) Download PDF for Graph Theory for the Secondary School Classroom. (opens in a new tab)

  9. Optimization in Geometric Graphs: Complexity and Approximation

    … including maximum independent set, minimum vertex coloring, minimum clique partition, max-cut and min-bisection. Although these problems have been widely studied in the context of unit disk graphs, which are the two dimensional version of unit ball graphs, there is no established result on …

    tamu Repository record for Optimization in Geometric Graphs: Complexity and Approximation (opens in a new tab)

  10. The power of locality: exploring the limits of randomness in distributed computing

    … many classic distributed graph problems such as vertex coloring, edge coloring, degree splittings and the approximation of linear programs. Furthermore, we provide a lower bound on the locality to compute certain vertex colorings in a weak variant of the LOCAL model.<br><br>It has been known for …

    freiburg-diss Repository record for The power of locality: exploring the limits of randomness in distributed computing (opens in a new tab)

  11. Scheduling in computer and communication systems and generalized graph coloring problems

    … weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In these …

    greece Repository record for Scheduling in computer and communication systems and generalized graph coloring problems (opens in a new tab)

  12. Pattern sequencing models in cutting stock problems

    … adding the representatives formulation for the vertex coloring problem. The model is applied to the minimization of open stacks, and also to the minimum interval graph completion problem and other pattern sequencing problems such as the minimization of the order spread (MORP) and the …

    minho-thes Repository record for Pattern sequencing models in cutting stock problems (opens in a new tab)

  13. Parallel Algorithms for Large Scale Dynamic Graph Analysis

    … and multi-objective shortest paths, as well as vertex coloring. Furthermore, using our shortest path update algorithms to determine efficient routes for drone-based deliveries under varying wind conditions accentuates the practicality and importance of our methods in dynamic environments. Our …

    must-thes Repository record for Parallel Algorithms for Large Scale Dynamic Graph Analysis (opens in a new tab)

  14. On b-colorings and b-continuity of graphs

    A b-coloring of G is a proper vertex coloring such that there is a vertex in each color class, which is adjacent to at least one vertex in every other color class. Such a vertex is called a color-dominating vertex. The b-chromatic number of G is the largest k such that there is a b-coloring of G by …

    qucosa-diss

  15. Sublinear Algorithm And Lower Bound For Combinatorial Problems

    … models.We first consider two graph problems, vertex coloring problem and metric traveling salesman problem (TSP). The main results are structure results for these problems, which give frameworks for achieving sublinear algorithms of these problems in different models. We also show that the …

    penn Repository record for Sublinear Algorithm And Lower Bound For Combinatorial Problems (opens in a new tab)

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

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

  17. Hall's condition and list coloring.

    … {dollar}v\\in 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 …

    wvu Repository record for Hall's condition and list coloring. (opens in a new tab)

  18. Monochromatic Subgraphs in Multiplex Networks

    … graph $H$ in $G_n$ in a uniformly random $c_n$-coloring of the vertices of $G_n$. In this dissertation we study the joint distribution of monochromatic subgraphs for dense multiplex networks, that is, networks with multiple layers. Specifically, given a finite collection of graphs …

    penn Repository record for Monochromatic Subgraphs in Multiplex Networks (opens in a new tab)

  19. Distributed graph algorithms under the challenges of locality, congestion, determinism, and dynamicity

    … provide an efficient deterministic algorithm for vertex coloring under bandwidth restrictions and algorithms for coloring and maximal independent set in highly dynamic networks.

    freiburg-diss Repository record for Distributed graph algorithms under the challenges of locality, congestion, determinism, and dynamicity (opens in a new tab)

  20. Coloração total em grafos potência de ciclo

    … in the literature, in particular with respect to coloring problems, and both vertex-coloring and edge-coloring problems have been solved in the class. The total-coloring problem, however, is still open for power of cycle graphs. Although recent works from Campos and de Mello [9] and from Almeida …

    brazil-uerj Repository record for Coloração total em grafos potência de ciclo (opens in a new tab)

Page 1 of 2