Computational complexity of compaction to irreflexive cycles

DOI10.1016/S0022-0000(03)00034-5zbMATH Open1069.68053MaRDI QIDQ596309FDOQ596309

Authors: Narayan Vikas 

Publication date: 10 August 2004

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

Recommendations

• Computational Complexity of Compaction to Reflexive Cycles
• scientific article; zbMATH DE number 1305547
• On the complexity of orthogonal compaction
• scientific article
• scientific article; zbMATH DE number 769607
• scientific article; zbMATH DE number 2188410
• Computational complexity of fixed points and intersection points
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Computational complexity of fixed points
• The complexity of some complementation problems

Mathematics Subject Classification ID

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

Cites Work

• On the complexity of H-coloring
• Parallel concepts in graph theory
• List homomorphisms and circular arc graphs
• Absolute reflexive retracts and absolute bipartite retracts
• List homomorphisms to reflexive graphs
• Fixed-edge theorem for graphs with loops
• Title not available (Why is that?)
• Computational Complexity of Compaction to Reflexive Cycles
• Absolute retracts of bipartite graphs
• Absolute Retracts and Varieties of Reflexive Graphs
• Title not available (Why is that?)
• A characterization of absolute retracts of n-chromatic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

• Surjective \texttt{H}-colouring over reflexive digraphs
• The complexity of surjective homomorphism problems-a survey
• Mixing 3-Colourings in Bipartite Graphs
• Algorithms for partition of some class of graphs under compaction
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• Title not available (Why is that?)
• Mixing 3-colourings in bipartite graphs
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• The complexity of counting surjective homomorphisms and compactions
• Computational complexity relationship between compaction, vertex-compaction, and retraction
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• Computational Complexity of Compaction to Reflexive Cycles
• Algorithms for partition of some class of graphs under compaction and vertex-compaction

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

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