Computational complexity of compaction to irreflexive cycles

DOI10.1016/S0022-0000(03)00034-5zbMath1069.68053MaRDI QIDQ596309

Narayan Vikas

Publication date: 10 August 2004

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Unnamed Item ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Mixing 3-Colourings in Bipartite Graphs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Mixing 3-colourings in bipartite graphs ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Parallel concepts in graph theory
• Absolute retracts of bipartite graphs
• List homomorphisms and circular arc graphs
• Absolute Retracts and Varieties of Reflexive Graphs
• Fixed-edge theorem for graphs with loops
• Computational Complexity of Compaction to Reflexive Cycles

This page was built for publication: Computational complexity of compaction to irreflexive cycles