Containment relations in split graphs

DOI10.1016/J.DAM.2011.10.004zbMATH Open1237.05180OpenAlexW2167772458MaRDI QIDQ765349FDOQ765349

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding topological subgraphs is fixed-parameter tractable
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• The complexity of induced minors and related problems
• On graph contractions and induced minors
• Detecting induced subgraphs
• Edge Contractions in Subclasses of Chordal Graphs
• 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
• On miniaturized problems in parameterized complexity theory
• Contracting a Chordal Graph to a Split Graph or a Tree

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)