Boundary Classes of Planar Graphs

DOI10.1017/S0963548307008814zbMath1166.05016OpenAlexW2011241251MaRDI QIDQ3512606

Vadim V. Lozin

Publication date: 21 July 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548307008814

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 (8)

Tree-width dichotomy ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ A Boundary Property for Upper Domination ⋮ Boundary Properties of Factorial Classes of Graphs

Cites Work

• Computing independent sets in graphs with large girth
• Treewidth for graphs with small chordality
• Independent domination in finitely defined classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Diameter and treewidth in minor-closed graph families, revisited
• On maximum induced matchings in bipartite graphs
• Upper bounds to the clique width of graphs
• Rank-width and vertex-minors
• Edge Dominating Sets in Graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

This page was built for publication: Boundary Classes of Planar Graphs