2014/03/14 by Richard Montgomery, Montgomery, Richard
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.1403.3548
11 pages
arxiv created 2014/12/15 · arxiv updated 2014/12/16
A symmetric m× m matrix M with entries taken from \0,1,∗\ gives rise to a graph partition problem, asking whether a graph can be partitioned into m vertex sets matched to the rows (and corresponding columns) of M such that, if Mij=1, then any two vertices between the corresponding vertex sets are joined by an edge, and if Mij=0 then any two vertices between the corresponding vertex sets are not joined by an edge. The entry ∗ places no restriction on the edges between the corresponding sets. This problem generalises graph colouring and graph homomorphism problems. A graph with no M-partition but such that every proper subgraph does have an M-partition is called a minimal obstruction. Feder, Hell and Xie have defined friendly matrices and shown that non-friendly matrices have infinitely many minimal obstructions. They showed through examples that friendly matrices can have finitely or infinitely many minimal obstructions and gave an example of a friendly matrix with an NP-hard partition problem. Here we show that almost all friendly matrices have infinitely many minimal obstructions and an NP-hard partition problem.