Almost all friendly matrices have many obstructions

DOI10.1137/140960840MaRDI QIDQ5251620zbMATH OpenOpenAlexFDO

Authors Richard Montgomery

Publication date 20 May 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3548

zbMATH Keywords

friendly matricesgraph coloringgraph partitioningNP-complete problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A symmetric $mimesm$ matrix $M$ with entries taken from $0,1,ast$ 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 $M_{ij}=1$, then any two vertices between the corresponding vertex sets are joined by an edge, and if $M_{ij}=0$ then any two vertices between the corresponding vertex sets are not joined by an edge. The entry $ast$ 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.

Recommendations

• Matrix partitions with finitely many obstructions
• Matrix Partitions with Finitely Many Obstructions
• Matrix partitions of split graphs
• Matrix partitions of perfect graphs
• Obstructions to partitions of chordal graphs

Cites work

• Excluding Induced Subgraphs III: A General Asymptotic
• Graph partitions with prescribed patterns
• List matrix partitions of chordal graphs
• List Partitions
• Matrix partitions of split graphs
• Matrix Partitions with Finitely Many Obstructions
• On the complexity of H-coloring
• The structure of hereditary properties and 2-coloured multigraphs
• The structure of hereditary properties and colourings of random graphs

Cited in

(1)

• Matrix partitions with finitely many obstructions

This page was built for publication: Almost all friendly matrices have many obstructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251620)