Sökning: "graph coloring"

Visar resultat 1 - 5 av 8 avhandlingar innehållade orden graph coloring.

  1. 1. On some graph coloring problems

    Författare :Carl Johan Casselgren; Roland Häggkvist; Svante Linusson; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; List coloring; interval edge coloring; coloring graphs from random lists; biregular graph; avoiding arrays; Latin square; scheduling; Discrete mathematics; Diskret matematik; Mathematics; matematik;

    Sammanfattning : .... LÄS MER

  3. 2. Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness

    Författare :Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Combinatorial optimization; approximation; inapproximability; hardness; probabilistically checkable proofs; pcp; perfect completeness; boolean constraint satisfaction problem; csp; graph coloring; hypergraph coloring; direct sum; superposition; label cover; Computer Science; Datalogi;

    Sammanfattning : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. LÄS MER

  4. 3. On avoiding and completing colorings

    Författare :Lan Anh Pham; Klas Markström; Carl Johan Casselgren; Victor Falgas-Ravry; Roland Häggkvist; Kimmo Eriksson; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Graph coloring; precoloring; list assignment;

    Sammanfattning : All of my papers are related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend φ to a proper edge coloring of G which avoids L? In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. LÄS MER

  5. 4. Edge Precoloring Extension of Trees

    Författare :Fikre Bogale Petros; Carl Johan Casselgren; Armen Asratian; Lars-Daniel Öhman; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : Given a set of k colors and a graph G with a subset S of precolored edges (a partial k-edge coloring of G), we consider the problem of determining whether G has a proper edge coloring of G with the same k colors (an extension of the partial coloring) where the colors of edges in S are not changed. If such a coloring exists, then the partial k-coloring is called extendable. LÄS MER

  7. 5. On avoiding and completing edge colorings

    Författare :Lan Anh Pham; Klas Markström; Svante Linusson; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Mathematics; matematik;

    Sammanfattning : These papers are all related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend the precoloring to a proper edge coloring avoiding any list assignment? In the first paper, G is a d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and every list assignment L must satisfy certain sparsity conditions. LÄS MER