Absolute Retracts and Varieties of Reflexive Graphs
Let H be a subgraph of G. The graph H is said to be a retract of G if there is an edge-preserving map f of G to H such that \(f(h)=h\) for each vertex h of H. A triple of H is a set of three vertices a, b, c of H together with three nonnegative integers i, j, k such that no vertex of H satisfies \(d_ H(h,a)\leq i\), \(d_ H(h,b)\leq j\), and \(d_ H(h,c)\leq k.\) The triple (a,b,c;i,j,k) of H is said to be separated in G if there is no vertex g of G satisfying \(d_ G(g,a)\leq i\), \(d_ G(g,b)\leq j\), \(d_ G(g,c)\leq k.\) The authors give a characterization (in terms of varieties) of each graph in which all triples of H are separated. Further results concern absolute retracts and the so-called finite separation property.
- scientific article; zbMATH DE number 844507
- Dismantling absolute retracts of reflexive graphs
- Absolute retracts and varieties generated by chordal graphs
- Absolute retracts of bipartite graphs
- On retracts, absolute retracts, and foldings in cographs
- On retracts, absolute retracts, and folds in cographs
- Minimal extensions of graphs to absolute retracts
- Absolute retracts of split graphs
- Cohomological approach to reflexive graphs
- scientific article; zbMATH DE number 1563206
- A surprising permanence of old motivations (a not-so-rigid story)
- A retraction problem in graph theory
- A characterization of absolute retracts of n-chromatic graphs
- Holes in ordered sets
- Dismantling absolute retracts of reflexive graphs
- List homomorphisms to reflexive graphs
- Graphs with edge-preserving majority functions
- A new fixed point approach for stable networks and stable marriages
- Absolute retracts of split graphs
- On the natural imprint function of a graph
- Injective envelope of graphs and transition systems
- Absolute retracts of bipartite graphs
- Obituary: Ivan Rival
- Homomorphically full graphs
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- The algebra of metric betweenness. I: Subdirect representation and retraction
- Semilattice polymorphisms and chordal graphs
- Retractions onto series-parallel posets
- On the extension of vertex maps to graph homomorphisms
- Building blocks for the variety of absolute retracts
- Graph partitions with prescribed patterns
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Beyond Helly graphs: the diameter problem on absolute retracts
- Weakly Modular Graphs and Nonpositive Curvature
- First-order Definable Retraction Problems for Posets and Reflexive Graphs
- scientific article; zbMATH DE number 3962727 (Why is no real title available?)
- A Classification of Reflexive Graphs: The use of “Holes”
- scientific article; zbMATH DE number 4031751 (Why is no real title available?)
- Minimal extensions of graphs to absolute retracts
- scientific article; zbMATH DE number 40997 (Why is no real title available?)
- Product graph representations
- Retract‐collapsible graphs and invariant subgraph properties
- Colouring, constraint satisfaction, and complexity
- scientific article; zbMATH DE number 844507 (Why is no real title available?)
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Minimum violation vertex maps and their applications to cut problems
- Computational complexity relationship between compaction, vertex-compaction, and retraction
- Computational complexity of compaction to irreflexive cycles
- Graphs with \(G^p\)-connected medians
- Helly groups
- Absolute reflexive retracts and absolute bipartite retracts
- Retracts of strong products of graphs
- Two remarks on retracts of graph products
- Retract rigid Cartesian products of graphs
- Absolute retracts and varieties generated by chordal graphs
This page was built for publication: Absolute Retracts and Varieties of Reflexive Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3030858)