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

• 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?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• 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
• 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 Relationship Between Clique-Width and Treewidth
• On the clique-width of graph with few \(P_{4}\)'s
• The strong perfect graph theorem
• The structure of bull-free graphs II and III -- a summary
• Universally signable graphs

Cited in

(5)

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