CanaDAM 2011
University of Victoria, May 31 - June 3, 2011

Colourings, Independence, and (Forbidden) Subgraphs
Org: Ingo Schiermeyer (Technical University Freiberg, Germany)

STEPHAN MATOS CAMACHO, Technische Universität Bergakademie Freiberg
Stars in Minimum Rainbow Subgraphs  [PDF]

Let $G$ be an egde-coloured graph, then a minimum rainbow subgraph is a subgraph of smallest order containing exactly one edge of every colour. We will discuss a polynomial time algorithm using stars for approximating this problem.

ANJA KOHL, Technical University Bergakademie Freiberg
Investigating the $b$-chromatic number of bipartite graphs by using the bicomplement  [PDF]

A \emph{$b$-coloring} of a graph $G$ by $k$ colors is a vertex coloring such that each color class contains a vertex that has neighbors in all other $k-1$ color classes. The \emph{$b$-chromatic number} $\chi_b(G)$ is the maximum integer $k$ for which $G$ has a $b$-coloring by $k$ colors. In this talk, we investigate $\chi_b(G)$ for bipartite graphs $G=(A\cup B,E)$ by considering the \emph{bicomplement} $\widetilde{G}=(A\cup B,\widetilde{E})$ with $\widetilde{E}:=\{\{a,b\}\mid a\in A, \ b\in B, \ \{a,b\}\notin E\}$.

VADIM LOZIN, University of Warwick
Vertex 3-colorability of claw-free graphs  [PDF]

The vertex 3-colorability problem is NP-hard in the class of claw-free graphs, since it includes, as a subproblem, the edge 3-colorability of general graphs. We study the computational complexity of the problem in subclasses of claw-free graphs defined by additional forbidden induced subgraphs and obtain a number of positive (polynomially solvable) and negative (NP-hard) results of this type. Joint work with Christopher Purcell

INGO SCHIERMEYER, Technical University Freiberg, Germany
Graphs with rainbow connection number two  [PDF]

An edge-coloured graph $G$ is {\it rainbow-connected} if any two vertices are connected by a path whose edges have distinct colours. The {\it rainbow connection number} $rc(G)$ of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ rainbow-connected. We characterize connected graphs with rainbow connection number $rc(G) = 2.$

Handling of online submissions has been provided by the CMS.

Event Sponsors

Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Victoria