The Library
Polarity of chordal graphs
Tools
Ekim, Tınaz, Hell, Pavol, Stacho, Juraj and de Werra, Dominique (2008) Polarity of chordal graphs. Discrete Applied Mathematics, Vol.156 (No.13). pp. 2469-2479. doi:10.1016/j.dam.2008.01.026 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2008.01.026
Abstract
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.156 | ||||
Number: | No.13 | ||||
Page Range: | pp. 2469-2479 | ||||
DOI: | 10.1016/j.dam.2008.01.026 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |