| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418632 | Discrete Applied Mathematics | 2010 | 6 Pages |
Abstract
An ii-triangulated graph is a graph in which every odd cycle has two non-crossing chords; ii-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced kk-partite subgraph of an ii-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Louigi Addario-Berry, W.S. Kennedy, Andrew D. King, Zhentao Li, Bruce Reed,