 english accueil réunion accueil canadam

Colourings and homomorphisms
Org: Gary MacGillivray (University of Victoria)
[PDF]

DEBRA BOUTIN, Hamilton College
Geometric Homomorphisms and the Geochromatic Number  [PDF]

A geometric graph $\overline G$ is a simple graph $G$ together with a fixed straightline drawing in the plane. A geometric homomorphism is a homomorphism of the underlying abstract graphs that also preserves edge crossings. Like the chromatic number of an abstract graph, the geochromatic number is defined using homomorphisms: the geochromatic number of a geometric graph $\overline G$ is the smallest integer $n$ so that there is a geometric homomorphism from $\overline G$ to some geometric realization of $K_n$. This talk will consider conditions under which we can find or bound the geometric chromatic number of a geometric graph.

RICHARD BREWSTER, Thompson Rivers University
The complexity of signed graph homomorhpisms  [PDF]

A signed graph $(G,\Sigma)$ is a graph $G$ where each edge is given a sign, positive or negative; $\Sigma\subseteq E(G)$ denotes the set of negative edges. Central to signed graphs is the operation of resigning at a vertex.

An s-homomorphism from $(G, \Sigma)$ to $(H,\Pi)$ is a vertex map that preserves edges and their signs after possibly resigning at some vertices of $G$. We give a simple classification of the {\bf P}/{\bf NP}-complete dichotomy for the $(H,\Pi)$-colouring problem and a direct proof of the result.

This is joint work with Foucaud, Hell, Naserasr, and Siggers.

Define a $k$-colouring of a mixed graph to be a homomorphism to a $k$-vertex (complete) mixed graph. A simple colouring of a mixed graph is a homomorphism to a reflexive mixed graph. Intuitively one would expect the simple chromatic number of a family of mixed graphs to be less than the chromatic number -- surely allowing adjacent vertices to have the same colour will allow us to use fewer colours. In this talk we explore cases where our intuition fails us using via a connection between simple colouring and a directed bootstrap percolation process.
Given a graph G and ${\it I}$, the family of independent sets in G, a function f:${\it I}$ $\to {\mbox{ [0, }}\infty {\mbox{)}}$ is a fractional coloring if for each vertex v, the inequality 1 $\leq\ \sum\limits_{{\mbox{v}} \in I} {{\mbox{ f}}(I)}$ holds. Further, the weight of f is w(f) $= \sum\limits_{{\mbox{I}} \in I} {{\mbox{ f}}({\mbox{I}})}$. The fractional chromatic number, $\chi$$_{f}(G), is the minimum weight of all fractional colorings. We develop methods for producing upper bounds on \chi$$_{f}$. This leads to simple proofs for theorems similar to Grotzch's 3-colorability theorem and the five color theorem for planar graphs.
For a fixed graph $H$, the recolouring problem for $H$-colouring(i.e. homomorphisms to $H$) ask: given an irreflexive graph $G$ and two $H$-colourings $\phi$ and $\psi$ of $G$, is it possible to transform $\phi$ into $\psi$ by changing the colour of one vertex at a time such that all intermediate mappings are $H$-colourings? For a reflexive graph $G$, one requires the extra condition that the colour must be changed to a neighbour of its current colour.