Polar graphs and maximal independent sets

DOI10.1016/j.disc.2004.06.024zbMath1108.05071OpenAlexW2016723076MaRDI QIDQ860455

Raffaele Mosca, Vadim V. Lozin

Publication date: 9 January 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.06.024

zbMATH Keywords

polynomial-time algorithmNP-hard

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Monopolar graphs: complexity of computing classical graph parameters ⋮ On the complexity of the independent set problem in triangle graphs ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs

Cites Work

• Unnamed Item
• Satgraphs and independent domination. I
• Domination in convex and chordal bipartite graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Modular decomposition and transitive orientation
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Bisplit graphs

This page was built for publication: Polar graphs and maximal independent sets