• Calendar

February 11, Wednesday
12:00 – 13:00

The Black-and-White Coloring (BWC) problem is defined as follows. Given an undirected graph $G$ and positive integers $b, w$, determine whether there exists a partial vertex-coloring of $G$ such that $b$ vertices are colored black and $w$ vertices white (with all other vertices left uncolored), such that no black vertex and white vertex are adjacent.

The BWC problem has been introduced in general, and proved to be $NP$-complete, by Hansen, Hertz and Quinodoz, who also gave an $O(n^3)$ algorithm for trees. In this talk we introduce another algorithm, whose running time is $O(n^2 lg ^3 n)$. We also present an improvement to our algorithm, which works for almost all labelled trees in time~$n^{1+o(1)}$.

If time permits, we will present an algorithm which solves the BWC problem for chordal graphs.