Computational complexity of compaction to irreflexive cycles
From MaRDI portal
Publication:596309
DOI10.1016/S0022-0000(03)00034-5zbMath1069.68053MaRDI QIDQ596309
Publication date: 10 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
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, Mixing 3-Colourings in Bipartite Graphs
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