The Star and Biclique Coloring and Choosability Problems

MARINA GROSHAUS; FRANCISCO J. SOULIGNAC; PABLO TERLISKY

Journal of graph algorithms and applications

Brown University

Año: 2014 vol. 18 p. 347 - 383

1526-1719

A biclique of a graph $G$ is an induced complete bipartite graph.  A star of $G$ is a biclique contained in the closed neighborhood of a vertex.  A star (biclique) $k$-coloring of $G$ is a $k$-coloring of $G$ that contains no monochromatic maximal stars (bicliques).  Similarly, for a list assignment $L$ of $G$, a star (biclique) $L$-coloring is an $L$-coloring of $G$ in which no maximal star (biclique) is monochromatic.  If $G$ admits a star (biclique) $L$-coloring for every $k$-list assignment $L$, then $G$ is said to be star (biclique) $k$-choosable.  In this article we study the computational complexity of the star and biclique coloring and choosability problems.  Specifically, we prove that the star (biclique) $k$-coloring and $k$-choosability problems are $Sigma_2^p$-complete  and $Pi_3^p$-complete for $k > 2$, respectively, even when the input graph contains no induced $C_4$ or $K_{k+2}$.   Then, we study all these problems in some related classes of graphs, including $H$-free graphs for every $H$ on three vertices, graphs with restricted diamonds, split graphs, and threshold graphs.