Name
Abstract | ||
|---|---|---|
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 NP -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 P n k is max ( 2 k + 2 - n , 2 ) if n ¿ 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 ¿ 2 k + 2 and exactly n 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2014.05.001 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Power of a cycle,Power of a path,Hypergraph,Biclique-colouring | Graph,Discrete mathematics,Complete bipartite graph,Combinatorics,Monochromatic color,Vertex (geometry),Bipartite graph,Hypergraph,Mathematical proof,co-NP,Mathematics | Journal |
Volume | Issue | ISSN |
192 | C | 0166-218X |
Citations | PageRank | References |
2 | 0.38 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hélio B. Macêdo Filho | 1 | 7 | 1.85 |
| Simone Dantas | 2 | 119 | 24.99 |
| Raphael C. S. Machado | 3 | 48 | 17.29 |
| Celina M. H. de Figueiredo | 4 | 296 | 38.49 |