×

Polarity of chordal graphs. (English) Zbl 1163.05051

Summary: 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brown, Jason I.; Corneil, Derek G., On generalized graph colorings, J. Graph Theory, 11, 87-99 (1987) · Zbl 0608.05035
[2] T. Ekim, N.V.R. Mahadev, D. de Werra, Polar cographs, Discrete Appl. Math., in press (doi:10.1016/j.dam.2007.08.025); T. Ekim, N.V.R. Mahadev, D. de Werra, Polar cographs, Discrete Appl. Math., in press (doi:10.1016/j.dam.2007.08.025) · Zbl 1136.05316
[3] Chernyak, Z. A.; Chernyak, A. A., About recognizing (a, b)-classes of polar graphs, Discrete Math., 62, 133-138 (1986) · Zbl 0606.05058
[4] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of graph partition problems, (31st Annual ACM STOC (1999)), 464-472 · Zbl 1345.68171
[5] Feder, T.; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., List matrix partitions of chordal graphs, Theoret. Comput. Sci., 349, 52-66 (2005) · Zbl 1084.05026
[6] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 2450-2460 (2006) · Zbl 1143.05035
[7] Farrugia, A., Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, Electron. J. Combin., 11 (2004) · Zbl 1053.05046
[8] Gagarin, A. V., Chordal \((1, \beta)\)-polar graphs, Vestsi Nats. Akad. Navuk Belarusi Ser. Fiz.-Mat. Navuk, 143, 115-118 (1999)
[9] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[10] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[11] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097
[12] Rosenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, vol. 1 (1997), Foundations World Scientific
[13] J. Stacho, Complexity of Generalized Colourings of Chordal Graphs, Ph.D. Thesis, Simon Fraser University, 2008; J. Stacho, Complexity of Generalized Colourings of Chordal Graphs, Ph.D. Thesis, Simon Fraser University, 2008 · Zbl 1136.68463
[14] Tarjan, R. E., Depth first search and linear graph algorithms, SIAM J. Comput., 1, 146-160 (1972) · Zbl 0251.05107
[15] Tarjan, R. E.; Yannakakis, M., Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062
[16] Tarjan, R. E.; Yannakakis, M. Y., Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 14, 254-255 (1985) · Zbl 0562.68055
[17] Tyshkevich, R. I.; Chernyak, A. A., Algorithms for the canonical decomposition of a graph and recognizing polarity, Izvestia Akad. Nauk BSSR, ser. Fiz. Mat. Nauk., 6, 16-23 (1985), (in Russian) · Zbl 0605.05041
[18] West, D., Introduction to Graph Theory (1996), Prentice Hall · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.