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 egdecoloured 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 $k1$ 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 3colorability of clawfree graphs [PDF]

The vertex 3colorability problem is NPhard
in the class of clawfree graphs, since it includes, as a subproblem,
the edge 3colorability of general graphs. We study the computational
complexity of the problem in subclasses of clawfree graphs defined
by additional forbidden induced subgraphs and obtain a number of positive
(polynomially solvable) and negative (NPhard) results of this type.
Joint work with Christopher Purcell
 INGO SCHIERMEYER, Technical University Freiberg, Germany
Graphs with rainbow connection number two [PDF]

An edgecoloured graph $G$ is {\it rainbowconnected} 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$ rainbowconnected. We characterize connected graphs with
rainbow connection number $rc(G) = 2.$
Handling of online submissions has been provided by the CMS.