Graphs of separability at most two: structural characterizations and their consequences

DOI10.1007/978-3-642-19222-7_30zbMATH Open1326.05127OpenAlexW2168666129MaRDI QIDQ3000517FDOQ3000517

Authors: Ferdinando Cicalese, Martin Milanič 

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_30

Recommendations

• Graphs of separability at most 2
• On the separability of graphs
• Path Separability of Graphs
• When all minimal \(k\)-vertex separators induce complete or edgeless subgraphs
• Graphs with complete minimal \(k\)-vertex separators.

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Cites Work

• Decomposition by clique separators
• Linear time solvable optimization problems on graphs of bounded clique-width
• A New Algorithm for Generating All the Maximal Independent Sets
• Title not available (Why is that?)
• On the Relationship Between Clique-Width and Treewidth
• The structure of bull-free graphs II and III -- a summary
• On rigid circuit graphs
• The strong perfect graph theorem
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Title not available (Why is that?)
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On graphs with polynomially solvable maximum-weight clique problem
• Claw-free graphs. IV: Decomposition theorem
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• On the clique-width of graph with few \(P_{4}\)'s
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Universally signable graphs
• Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
• A theorem of Truemper
• Even-hole-free graphs. I: Decomposition theorem
• Isomorphism of graphs which are pairwise k-separable
• Even and odd holes in cap-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Separation index of a graph
• Graphs of separability at most 2
• Title not available (Why is that?)
• On the separability of graphs
• On seed graphs with more than two components

This page was built for publication: Graphs of separability at most two: structural characterizations and their consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000517)