On retracts, absolute retracts, and foldings in cographs

DOI10.1007/s11590-017-1126-9zbMath1393.05187OpenAlexW163950404MaRDI QIDQ1749782

Ton Kloks, Yue-Li Wang

Publication date: 28 May 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1126-9

zbMATH Keywords

cographsfoldingsretractsabsolute retracts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Beyond Helly graphs: the diameter problem on absolute retracts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The core of a graph
• Finding vertex-surjective graph homomorphisms
• Parameterized graph cleaning problems
• Approximate labelled subtree homeomorphism
• A characterization of absolute retracts of n-chromatic graphs
• A lower estimate for the achromatic number of irreducible graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Trivially perfect graphs
• Absolute retracts of bipartite graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Cleaning interval graphs
• List homomorphisms and circular arc graphs
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Exact algorithms for graph homomorphisms
• Retracts of hypercubes
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• A Linear Recognition Algorithm for Cographs
• O(n2.5) time algorithms for the subgraph homeomorphism problem on trees
• An Analysis of a Good Algorithm for the Subtree Problem
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Perfect Elimination and Chordal Bipartite Graphs
• Ordered and Unordered Tree Inclusion
• Faster Subtree Isomorphism
• Paths, Trees, and Flowers
• A Note on "The Comparability Graph of a Tree"
• The achromatic number of a graph

This page was built for publication: On retracts, absolute retracts, and foldings in cographs