A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results

DOI10.1016/j.jcss.2004.07.003zbMath1101.68613OpenAlexW2051028069MaRDI QIDQ2575831

Narayan Vikas

Publication date: 7 December 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.07.003

zbMATH Keywords

Computational complexityGraphHomomorphismPartitionRetractionColouringCompaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Unnamed Item ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ On the sum-max graph partitioning problem ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Surjective \(H\)-colouring: new hardness results ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Retracting Graphs to Cycles ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of compaction to irreflexive cycles
• Absolute reflexive retracts and absolute bipartite retracts
• A characterization of absolute retracts of n-chromatic graphs
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Colorings and interpretations: a connection between graphs and grammar forms
• Parallel concepts in graph theory
• Absolute retracts of bipartite graphs
• List homomorphisms and circular arc graphs
• Complexity of graph partition problems
• Absolute Retracts and Varieties of Reflexive Graphs
• Classification and detection of obstructions to planarity
• Fixed-edge theorem for graphs with loops
• A graph coloring algorithm for large scheduling problems
• An application of graph coloring to printed circuit testing
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• Computing and Combinatorics
• Computational Complexity of Compaction to Reflexive Cycles
• Monotone monadic SNP and constraint satisfaction

This page was built for publication: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results