Anticoloring Problems on General and Special Graphs

Abstract

An {\it anticoloring} of a graph is a coloring of some of the vertices,
in which no two adjacent vertices are colored in {\it distinct} colors.
In the basic version of the {\it anticoloring problem} we are given a
graph $G$ and positive integers $B_1, ..., B_k$ and we have to determine
whether there exists an anticoloring of $G$ such than $B_j$ vertices are
colored in color $j$, $j = 1, ..., k$. This problem is known to be
$NP$-complete, even for two colors.

We present slightly different versions of the anticoloring problem and
prove their polynomiality for two colors, through both linear programming
and combinatorial algorithms.

In addition, we study the basic version of the anticoloring problem for
special graphs arising from the problem of placing non-attacking black
and white rooks on a rectangular chessboard. We give sublinear algorithms
and even closed-form solutions for several instances of the problem.