Biclique-Coloring

MARINA GROSHAUS; FRANCISCO J. SOULIGNAC; PABLO TERLISKY

Rio de Janeiro

Workshop; Latin American Workshop on Cliques in Graphs 2010; 2010

A $k$-clique-coloring of a graph is an assignment of $k$ colors to its vertices such that every clique has at least two vertices with different colors. For $k geq 2$, the problem of deciding if a graph is $k$-clique-colorable is $Sigma^p_2$-complete, though it is easier for some graph classes.In this work, we study the computational complexity of the $k$-biclique-coloring problem, which we define as the analogue of the $k$-clique-coloring for bicliques.  That is, a $k$-biclique-coloring of a graph is an assignment of $k$ colors to its vertices such that every biclique has at least two vertices with different colors.We prove that the $k$-biclique-coloring problem is $Sigma^p_2$-complete for $k geq 2$, even for $K_{3,3}$-free graphs, and show that it is NP-Complete for $k geq 2$ on the class of split graphs and for $k=2$ on the class of $(W_4, extrm{ extsl{dart}}, extrm{ extsl{gem}})$-free graphs. Also, we show that it can be solved in polynomial time for threshold graphs, block graphs and graphs in which every edge belongs to a single biclique.