Graphs of separability at most 2

DOI10.1016/j.dam.2011.01.016zbMath1241.05142OpenAlexW1968107207MaRDI QIDQ415268

Ferdinando Cicalese, Martin Milanič

Publication date: 11 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.01.016

zbMATH Keywords

decompositionseparabilityinduced subgraphhereditary classinduced minorparsimony haplotypingseparating clique

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Related Items (9)

Unnamed Item ⋮ The expansion of polynomial invariants for $2$-decompositions of generalized graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ Algorithmic results on locating-total domination in graphs ⋮ Substitution and \(\chi\)-boundedness ⋮ The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs ⋮ Secure total domination in graphs: bounds and complexity ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• On rigid circuit graphs
• The strong perfect graph theorem
• Claw-free graphs. IV: Decomposition theorem
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Decomposition by clique separators
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Some simplified NP-complete graph problems
• 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
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Even-hole-free graphs part I: Decomposition theorem
• Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
• Isomorphism of graphs which are pairwise k-separable
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Even and odd holes in cap-free graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• A mickey-mouse decomposition theorem
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• On the Relationship Between Clique-Width and Treewidth

This page was built for publication: Graphs of separability at most 2