Almost All Friendly Matrices Have Many Obstructions

DOI10.1137/140960840zbMath1311.05165arXiv1403.3548OpenAlexW2025505588MaRDI QIDQ5251620

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

graph coloringgraph partitioningNP-complete problemfriendly matrices

Mathematics Subject Classification ID

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

Cites Work

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

This page was built for publication: Almost All Friendly Matrices Have Many Obstructions