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.