Biclique-colouring powers of paths and powers of cycles

Details Biclique-colouring powers of paths and powers of cycles Biclique-colouring powers of paths and powers of cycles

2012-03-12

arxiv.org/abs/1203.2543v1

Computer Science

Data Structures and Algorithms

23 pages, 8 figures

Scientific paper

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$\mathcal{NP}$-complete to check if a colouring of vertices is a valid 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 $P_{n}^{k}$ is $\max(2k + 2 - n, 2)$ if $n \geq k + 1$ and exactly $n$ otherwise. The biclique-chromatic number of a power of a cycle $C_n^k$ is at most 3 if $n \geq 2k + 2$ and exactly $n$ otherwise; we additionally determine the powers of cycles that are 2-biclique-colourable. All the proofs are algorithmic and we provide polynomial-time biclique-colouring algorithms for graphs in the investigated classes.

Affiliated with

Also associated with

No associations

Rating

Biclique-colouring powers of paths and powers of cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Biclique-colouring powers of paths and powers of cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Biclique-colouring powers of paths and powers of cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488653