Biclique-colouring verification complexity and biclique-colouring power graphs

Biclique-colouring is a colouring of the vertices of a graph in such a way that no maximal complete bipartite subgraph with at least one edge is monochromatic. We show that it is co-complete to check whether a given function that associates a colour to each vertex is a biclique-colouring, a result that justifies the search for structured classes where the biclique-colouring problem could be efficiently solved. We consider biclique-colouring restricted to powers of paths and powers of cycles. We determine the biclique-chromatic number of powers of paths and powers of cycles. The biclique-chromatic number of a power of a path is if and exactly otherwise. The biclique-chromatic number of a power of a cycle is at most 3 if and exactly otherwise; we additionally determine the powers of cycles that are 2-biclique-colourable. All proofs are algorithmic and provide polynomial-time biclique-colouring algorithms for graphs in the investigated classes.