×

Absolute retracts and varieties of reflexible graphs. (English) Zbl 0627.05039

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.
Reviewer: J.Širáň

MSC:

05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI