Graphs of separability at most 2

DOI10.1016/j.dam.2011.01.016zbMath1241.05142MaRDI 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

decomposition; separability; induced subgraph; hereditary class; induced minor; parsimony haplotyping; separating clique

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C75: Structural characterization of families of graphs

05C99: Graph theory

Related Items

The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, Partial Characterizations of 1‐Perfectly Orientable Graphs, Hereditary Efficiently Dominatable Graphs, Substitution and \(\chi\)-boundedness, Secure total domination in graphs: bounds and complexity, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs

Cites Work

• Unnamed Item
• 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
• 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