Matrix partitions of split graphs

DOI10.1016/J.DAM.2013.10.016MaRDI QIDQ2636832zbMATH OpenOpenAlexFDO

Authors Tomás Feder, Oren Shklarsky, Pavol Hell

Publication date 18 February 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

forbidden subgraphsgeneralized graph colouringmatrix partitionminimal obstructionssplit graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Matrix partition problems generalize a number of natural graph partition problems, and have been studied for several standard graph classes. We prove that each matrix partition problem has only finitely many minimal obstructions for split graphs. Previously such a result was only known for the class of cographs. (In particular, there are matrix partition problems which have infinitely many minimal chordal obstructions.) We provide (close) upper and lower bounds on the maximum size of a minimal split obstruction. This shows for the first time that some matrices have exponential-sized minimal obstructions of any kind (not necessarily split graphs). We also discuss matrix partitions for bipartite and co-bipartite graphs.

Recommendations

• Matrix Partitions with Finitely Many Obstructions
• Obstructions to partitions of chordal graphs
• Matrix partitions with finitely many obstructions
• Minimal obstructions for a matrix partition problem in chordal graphs
• Matrix partitions of perfect graphs

Cites work

• Generalized colouring (matrix partitions) of cographs
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• List matrix partitions of chordal graphs
• List Partitions
• Matrix partitions of perfect graphs
• Matrix partitions with finitely many obstructions
• Obstructions to partitions of chordal graphs
• On realizations of point determining graphs, and obstructions to full homomorphisms
• The complexity of list edge-partitions for simple graphs

Cited in

(10)

• Matrix partitions with finitely many obstructions
• List matrix partitions of graphs representing geometric configurations
• Minimal obstructions for a matrix partition problem in chordal graphs
• Graph partitions with prescribed patterns
• Counting List Matrix Partitions of Graphs
• Generalized colouring (matrix partitions) of cographs
• Matrix Partitions with Finitely Many Obstructions
• Almost all friendly matrices have many obstructions
• Generalisations of matrix partitions: complexity and obstructions
• The complexity of list edge-partitions for simple graphs

This page was built for publication: Matrix partitions of split graphs

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