Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
From MaRDI portal
Publication:972337
DOI10.1016/j.dam.2008.08.020zbMath1216.05152OpenAlexW2090354123MaRDI QIDQ972337
Zhentao Li, Louigi Addario-Berry, Andrew D. King, Bruce A. Reed, W. Sean Kennedy
Publication date: 25 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.020
Related Items (11)
Reconfiguration of colorable sets in classes of perfect graphs ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ New characterizations of Gallai's \(i\)-triangulated graphs ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Inductive graph invariants and approximation algorithms ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Approximability of clique transversal in perfect graphs ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong perfect graph theorem
- Facets of the balanced (acyclic) induced subgraph polytope
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Polyhedral results for the bipartite induced subgraph problem
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Facets of the Bipartite Subgraph Polytope
- Graph Bipartization and via minimization
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
This page was built for publication: Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
