论文标题
在弦图中对矩阵分区问题的最小障碍物
Minimal obstructions for a matrix partition problem in chordal graphs
论文作者
论文摘要
如果$ m $是$ \ {0，1，1，\ ast \} $上的$ m \ times m $矩阵，则图$ g $的$ m $ - 分区是一个分区$（v_1，v_1 \ dots v_m）$ = 0 $），如果$ v_i $和$ v_j $之间没有进一步的限制，如果$ m_ {ij} = \ ast $。拥有$ m $ $的分区是一个世袭的财产，因此它的特征是一组最小的障碍物（禁止诱发的子图最小，而没有$ m $ $ $ - 分区的财产）。 众所周知，每3美元$ 3 $矩阵$ m $ of $ \ {0，1，\ ast \} $，对于确定图表是否承认$ m $分区的问题有限的最小障碍，除非两个矩阵，但两个矩阵，$ m_1 = \ weft（$ m_1 = \ lest（ \ ast＆0＆1 \\ \ ast＆1＆0 \ end {array} \ right）$和$ m_2 = \ left（\ begin {array} {array} {ccc} 0＆\ ast＆\ ast＆\ ast＆\ ast＆\ ast ast ast ast ast ast＆1对于这两个矩阵，无限的弦链最小障碍物是已知的（两个矩阵的家族），但一组最小的障碍物却不是。 在这项工作中，我们以$ m_1 $的价格介绍了完整的和弦最小障碍的家庭。
If $M$ is an $m \times m$ 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 $3 \times 3$ 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, $M_1 = \left( \begin{array}{ccc} 0 & \ast & \ast \\ \ast & 0 & 1 \\ \ast & 1 & 0 \end{array} \right)$ and $M_2 = \left( \begin{array}{ccc} 0 & \ast & \ast \\ \ast & 0 & 1 \\ \ast & 1 & 1 \end{array} \right)$. 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$.
