The Star and Biclique Coloring and Choosability Problems
Vol. 18, no. 3, pp. 347-383, 2014. Regular paper.
Abstract 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.
Submitted: November 2012.
Reviewed: March 2014.
Revised: March 2014.
Accepted: May 2014.
Final: May 2014.
Published: June 2014.
Communicated by Ken-ichi Kawarabayashi
article (PDF)