Polarity of chordal graphs
Polarity of chordal graphs
复制标题
弦图的极性
DOI：
10.1016/j.dam.2008.01.026
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Werra
中科院分区：
文献类型：
--
作者：
T. Ekim;P. Hell;J. Stacho;D. Werra
极坐标图是二部图、协部图和分割图的一般推广。它们是由一定的顶点划分的存在性来定义的，对于一般图来说，这个划分是np完全的。最近已经证明，对于图，这种划分的存在性可以用有限个禁止子图来表征，因此在多项式时间内得到了验证。在本文中，我们解决弦图的极性问题，认为这在本质上是一个可着色性问题，因此弦图是一个自然的限制。我们观察到弦图中极性不存在有限禁止子图表征；然而，我们提出了一个多项式时间算法来求解弦图的极性。我们专注于极性（称为单极性）的特殊情况，这是我们算法的中心概念。对于单极图，我们给出了所有最小障碍的结构；事实证明，它们都可以用特定的图语法来描述，从而允许将我们的单一性算法转换为证明算法。
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm.