Search for dissertations about: "List coloring"

Found 3 swedish dissertations containing the words List coloring.

  1. 1. On some graph coloring problems

    Author : Carl Johan Casselgren; Roland Häggkvist; Svante Linusson; Umeå universitet; []
    Keywords : NATURAL SCIENCES; NATURVETENSKAP; 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;

    Abstract : .... READ MORE

  2. 2. On avoiding and completing colorings

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

    Abstract : 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. READ MORE

  3. 3. On avoiding and completing edge colorings

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

    Abstract : 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. READ MORE