Containment relations in split graphs

DOI10.1016/J.DAM.2011.10.004MaRDI QIDQ765349zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Daniël Paulusma, Dimitrios M. Thilikos, Marcin Kamiński

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

contractionminorgraph operationssubgraphedge contractionstopological minoredge deletionsgraph containment problemvertex deletionsvertex dissolutions

Mathematics Subject Classification ID

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

Recommendations

• Obtaining split graphs by edge contraction
• Obtaining split graphs by edge contraction
• A note on contracting claw-free graphs
• Contracting a chordal graph to a split graph or a tree
• Detecting fixed patterns in chordal graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 139780 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Contractibility and NP-completeness
• Contracting a chordal graph to a split graph or a tree
• Contractions of Planar Graphs in Polynomial Time
• Edge contractions in subclasses of chordal graphs
• Finding contractions and induced minors in chordal graphs via disjoint paths
• Finding topological subgraphs is fixed-parameter tractable
• Graph Classes: A Survey
• Graph minors. XIII: The disjoint paths problem
• 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
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases

Cited in

(4)

• Detecting fixed patterns in chordal graphs in polynomial time
• Edge contractions in subclasses of chordal graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Induced disjoint paths in claw-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765349)