Containment relations in split graphs

DOI10.1016/j.dam.2011.10.004zbMath1237.05180OpenAlexW2167772458MaRDI QIDQ765349

Petr A. Golovach, Dimitrios M. Thilikos, Daniël Paulusma, Marcin Kaminski

Publication date: 19 March 2012

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

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

zbMATH Keywords

contractionminorsubgraphgraph operationsedge contractionstopological minoredge deletionsgraph containment problemvertex deletionsvertex dissolutions

Mathematics Subject Classification ID

Graph minors (05C83) Graph operations (line graphs, products, etc.) (05C76)

Related Items (4)

Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Edge contractions in subclasses of chordal graphs ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Induced Disjoint Paths in Claw-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graph contractions and induced minors
• On miniaturized problems in parameterized complexity theory
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• The complexity of induced minors and related problems
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Edge Contractions in Subclasses of Chordal Graphs
• Contracting a Chordal Graph to a Split Graph or a Tree
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Contractions of Planar Graphs in Polynomial Time
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness
• Graph Classes: A Survey
• Finding topological subgraphs is fixed-parameter tractable
• Detecting induced subgraphs

This page was built for publication: Containment relations in split graphs