Essays about: "Graph colouring"

Found 4 essays containing the words Graph colouring.

  1. 1. Upper bounds on the star chromatic index for bipartite graphs

    University essay from Linköpings universitet/Matematik och tillämpad matematik; Linköpings universitet/Tekniska fakulteten

    Author : Victor Melinder; [2020]
    Keywords : Graph Theory; Star edge colouring; Star chromatic index; Graph colouring; Biregular; Graph; Grafteori; stjärnkantsfärgning; stjärnkromatiskt index; graffärgning; Bireguljär; Graf;

    Abstract : An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. READ MORE

  3. 2. Observations on de Bruijn graphs

    University essay from Lunds universitet/Matematik LTH; Lunds universitet/Matematik (naturvetenskapliga fakulteten)

    Author : Jonathan Garbe; [2020]
    Keywords : de Bruijn graph; shift of finite type; symbolic dynamic; strongly connected graph; primitive graph; transitive shift; mixing shift; alternating colouring; Mathematics and Statistics;

    Abstract : Abstract of chapter 1 For n >= 2 the number of mixing n-step subshifts of finite type (sft) over the alphabet {0, 1} is proven to be at least 15/16 times the number of transitive n-step sfts. A conjecture assumes the latter to be at least 2^(3*2^(n-1)-n). Abstract of chapter 2 The alternating colouring function is defined. READ MORE

  4. 3. A Comparison of a Heuristic and a Hopfield Neural Network Approach for Solving Examination Timetabling Problems

    University essay from KTH/Skolan för elektroteknik och datavetenskap (EECS)

    Author : Maria Lindblad; [2019]
    Keywords : ;

    Abstract : The Examination Timetabling Problem (ETP) is the problem of scheduling a number of exams during a set time period so that no students are required to sit two exams simultaneously. Despite the complexity of the problem, universities all over the world solve ETPs several times each year. READ MORE

  5. 4. Study of efficient techniques for implementing a Pseudo-Boolean solver based on cutting planes

    University essay from KTH/Skolan för datavetenskap och kommunikation (CSC)

    Author : Aleix Sacrest Gascon; [2017]
    Keywords : ;

    Abstract : Most modern SAT solvers are based on resolution and CNF representation. The performance of these has improved a great deal in the past decades. But still they have some drawbacks such as the slow efficiency in solving some compact formulas e.g. READ MORE