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 3 of 3 for “"circular colouring"”.

  1. Density and Structure of Homomorphism-Critical Graphs

    … (or equivalently, has a $\tfrac{2t+1}{t}$-circular colouring). The best known result for the $t=3$ case states that every planar graph of girth at least 18 has a homomorphism to $C_7$. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to …

    waterloo Repository record for Density and Structure of Homomorphism-Critical Graphs (opens in a new tab)

  2. Finding Independent Transversals Efficiently

    … to solve problems in graph theory (e.g. list colouring, strong colouring, delay edge colouring, circular colouring, various graph partitioning and special independent set problems), hypergraphs (e.g. hypergraph matching), group theory (e.g. generators in linear groups), and theoretical …

    waterloo Repository record for Finding Independent Transversals Efficiently (opens in a new tab)

  3. Fractional refinements of integral theorems

    … to problems which partition the vertex set, circular colouring provides a way to fractionally refine colouring problems. A classic theorem of Tuza says that every graph with no cycles of length $1 \bmod k$ is $k$-colourable. Generalizing this to circular colouring, we get the following: Let …

    waterloo Repository record for Fractional refinements of integral theorems (opens in a new tab)