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

DOI10.1007/978-3-642-19222-7_30MaRDI QIDQ3000517zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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.

Cites work

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

Cited in

(5)

• On the separability of graphs
• Separation index of a graph
• scientific article; zbMATH DE number 4139782 (Why is no real title available?)
• Graphs of separability at most 2
• 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)