The Star and Biclique Coloring and Choosability Problems

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.