Absolute reflexive retracts and absolute bipartite retracts

DOI10.1016/0166-218X(93)90219-EzbMath0795.05133OpenAlexW1987058044MaRDI QIDQ686243

Martin Farber, Hans-Jürgen Bandelt, Pavol Hell

Publication date: 30 November 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90219-e

zbMATH Keywords

characterizationsbipartite graphsretractreflexive graphs

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (20)

On neighborhood-Helly graphs ⋮ Computational complexity of compaction to irreflexive cycles ⋮ Incidence graphs of biacyclic hypergraphs ⋮ List homomorphisms to reflexive graphs ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ List-homomorphism problems on graphs and arc consistency ⋮ Dually chordal graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Posets, clique graphs and their homotopy type ⋮ Biclique-Helly graphs ⋮ Absolute retracts and varieties generated by chordal graphs ⋮ Generating bicliques of a graph in lexicographic order ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Characterizing bipartite graphs which admit a \(k\)-NU polymorphism via absolute retracts ⋮ On the generation of bicliques of a graph ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Injective envelope of graphs and transition systems ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results ⋮ List homomorphism problems for signed trees

Cites Work

• Clique graphs and Helly graphs
• Pseudo-modular graphs
• A fixed cube theorem for median graphs
• Dismantling absolute retracts of reflexive graphs
• Classes of bipartite graphs related to chordal graphs
• Graphs with edge-preserving majority functions
• Absolute retracts of bipartite graphs
• Vertex-to-vertex pursuit in a graph
• The smallest graph variety containing all paths
• Absolute planar retracts and the four colour conjecture
• Absolute Retracts and Varieties of Reflexive Graphs
• Products of absolute retracts
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Absolute reflexive retracts and absolute bipartite retracts