CanaDAM 2011 Université de Victoria, 31 mai - 3 juin 2011 www.smc.math.ca//2011f

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

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\}$.

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.$