Minimal obstructions for a matrix partition problem in chordal graphs

2020/04/02 by Juan Carlos García-Altamirano, García-Altamirano, Juan Carlos, César Hernández‐Cruz +1
Engineering · Computer Science · #graph theory and CDMA systems #Advanced Graph Theory Research #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2004.01229

Abstract

If M is an m × m matrix over \ 0, 1, ∗ \, an M-partition of a graph G is a partition (V₁, … 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 = ∗. 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 3 × 3 matrix M over \ 0, 1, ∗ \, there are finitely many chordal minimal obstructions for the problem of determining whether a graph admits an M-partition, except for two matrices, M₁ = ( 0 · amp; ∗ · amp; ∗
∗ · amp; 0 · amp; 1
∗ · amp; 1 · amp; 0 ) and M₂ = ( 0 · amp; ∗ · amp; ∗
∗ · amp; 0 · amp; 1
∗ · amp; 1 · amp; 1 ). 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₁.

Related

• Matrix Partitions of Split Graphs
• Almost all friendly matrices have many obstructions
• Minimal digraph obstructions for small matrices
• Point determining digraphs, \0,1\-matrix partitions, and dualities in full homomorphisms
• On the Minimum Chordal Completion Polytope