Minimal obstructions for a matrix partition problem in chordal graphs

DOI10.1016/J.DAM.2022.09.012MaRDI QIDQ2097166zbMATH OpenOpenAlexFDO

Authors Juan Carlos García-Altamirano, César Hernández-Cruz

Publication date 11 November 2022

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

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

zbMATH Keywords

chordal graphforbidden induced subgraph characterizationmatrix partition\(M\)-partition

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: If $M$ is an $mimesm$ matrix over $0,1,ast$, an $M$-partition of a graph $G$ is a partition $(V_1,dots{V}_m)$ such that $V_i$ is completely adjacent (non-adjacent) to $V_j$ if $M_{ij}=1$ ($M_{ij}=0$), and there are no further restrictions between $V_i$ and $V_j$ if $M_{ij}=ast$. Having an $M$-partition is a hereditary property, thus it can be characterized by a set of minimal obstructions (forbidden induced subgraphs minimal with the property of not having an $M$-partition). It is known that for every $3imes3$ matrix $M$ over $0,1,ast$, there are finitely many chordal minimal obstructions for the problem of determining whether a graph admits an $M$-partition, except for two matrices, $$ and $$. For these two matrices an infinite family of chordal minimal obstructions is known (the same family for both matrices), but the complete set of minimal obstructions is not. In this work we present the complete family of chordal minimal obstructions for $M_1$.

Recommendations

• Obstructions to partitions of chordal graphs
• List matrix partitions of chordal graphs
• Partitioning chordal graphs
• Join colourings of chordal graphs
• Matrix partitions of split graphs

Cites work

• Graph partitions with prescribed patterns
• Graph theory
• Join colourings of chordal graphs
• List matrix partitions of chordal graphs
• Obstructions to partitions of chordal graphs
• Partitioning chordal graphs into independent sets and cliques
• Polarity of chordal graphs
• Probe split graphs

Cited in

(7)

• Graph partitions with prescribed patterns
• Join colourings of chordal graphs
• Generalized colouring (matrix partitions) of cographs
• On the characterization of graphs with an equivalence partition number at most three in the class of chordal graphs
• Matrix partitions of split graphs
• Obstructions to partitions of chordal graphs
• List matrix partitions of chordal graphs

This page was built for publication: Minimal obstructions for a matrix partition problem in chordal graphs

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