Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00326
The Star and Biclique Coloring and Choosability Problems
Vol. 18, no. 3, pp. 347383, 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
Kenichi Kawarabayashi
