The star and biclique coloring and choosability problems

MARINA GROSHAUS; FRANCISCO J. SOULIGNAC; PABLO TERLISKY

Buenos Aires

Workshop; Latin American Workshop on Cliques in Graphs, 2012; 2012

 In this work we study the computational complexity of the star and biclique coloring and choosability problems, which are analogous to the clique coloring and choosability problems.  A emph{biclique} of a graph $G$ is an induced complete bipartite graph with at least two vertices.  A emph{star} of $G$ is a biclique with a universal vertex.  A emph{star (resp. biclique) $k$-coloring} of $G$ is a $k$-coloring of $G$ that contains no monochromatic maximal stars (resp. bicliques).  Similarly, for a list assignment $Lcolon V(G) o mathcal{P}(mathbb{N})$ of $G$, a emph{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 list assignment $L$ such that$|L(v)| = k$ ($v in V(G)$), then $G$ is said to be emph{star (biclique) $k$-choosable}.      We prove that the star $k$-coloring and $k$-choosability problems are $Sigma_2^p$-complete and $Pi_3^p$-complete for $k > 2$, respectively, even when their inputs are restricted to graphs with no induced $C_4$ or $K_{k+2}$.   Every biclique of a $C_4$-free graph is a star, thus, as a corollary, we obtain that the biclique $k$-coloring and $k$-choosability problems on {$C_4$, $K_{k+2}$}-free graphs are also $Sigma_2^p$-complete and $Pi_3^p$-complete, respectively.  Following, we study all these problems considering the inputs are restricted to some related classes, including: $K_3$-free graphs; $P_3$-free graphs; $overline{P_3}$-free graphs; co-bipartite graphs; graphs with no induced $4$-wheels, gems, or darts; split graphs; threshold graphs; and block graphs.