Bandelt, Hans-Jürgen; Farber, Martin; Hell, Pavol Absolute reflexive retracts and absolute bipartite retracts. (English) Zbl 0795.05133 Discrete Appl. Math. 44, No. 1-3, 9-20 (1993). A subgraph \(G=(V,E)\) of \(G'=(V',E')\) is a retract of \(G'\) if there is some edge-preserving mapping \(f:V' \to V\) such that \(f(x)=x\) for a every \(x \in V\). An absolute reflexive (respectively bipartite) retract is a reflexive (respectively bipartite) graph \(G\) with the property that if \(G\) is an isometric subgraph of some reflexive (respectively bipartite) graph \(G'\), then \(G\) is a retract of \(G'\). Several characterizations of absolute reflexive retracts or absolute bipartite retracts are known. These characterizations are very similar. In the paper under review, this connection is made explicit in the following sense: Four transformations between the class of reflexive graphs and the class of bipartite graphs are presented. Well known are the bigraph \(B(G)\) and the vertex-clique incidence graph \(I(G)\) of a reflexive graph \(G\). Conversely, if \(H\) is a bipartite graph with given bipartition \(X \cup Y\), then the sesqui-power \(S_ X (H)\) is the reflexive graph with vertex set \(X\cup Y\) and two vertices adjacent if their \(H\)-distance is at most 1, or if both belong to \(X\) and their \(H\)-distance is at most 2. The sesqui-power \(S_ Y (H)\) is defined analogously. The edge graph \(E(H)\) has the edges of \(H\) as vertices, and two such vertices are adjacent in \(E(H)\) whenever the corresponding edges intersect, or lie on a 4-cycle of \(H\).It is shown that these transformations map absolute reflexive retracts into absolute bipartite retracts, and conversely. Moreover, also the ingredients of the characterizations behave in this sense under the transformations. Reviewer: E.Prisner (Hamburg) Cited in 20 Documents MSC: 05C99 Graph theory Keywords:retract; characterizations; reflexive graphs; bipartite graphs PDFBibTeX XMLCite \textit{H.-J. Bandelt} et al., Discrete Appl. Math. 44, No. 1--3, 9--20 (1993; Zbl 0795.05133) Full Text: DOI References: [1] Bandelt, H.-J., Graphs with edge-preserving majority functions, Discrete Math., 103, 1-5 (1992) · Zbl 0766.05024 [2] Bandelt, H.-J.; Dählmann, A.; Schütte, H., Absolute retracts of bipartite graphs, Discrete Appl. Math., 16, 191-215 (1987) · Zbl 0614.05046 [3] Bandelt, H.-J.; Mulder, H. M., Pseudo-modular graphs, Discrete Math., 62, 245-260 (1986) · Zbl 0606.05053 [4] Bandelt, H.-J.; Pesch, E., Dismantling absolute retracts of reflexive graphs, European J. Combin., 10, 211-220 (1989) · Zbl 0674.05065 [5] Bandelt, H.-J.; Prisner, E., Clique graphs and Helly graphs, J. Combin. Theory Ser. B, 51, 34-45 (1991) · Zbl 0726.05060 [6] Bandelt, H.-J.; van de Vel, M., A fixed cube theorem for median graphs, Discrete Math., 67, 129-137 (1987) · Zbl 0628.05053 [7] Bélanger, M.-F.; Constantin, J.; Fournier, G., Graphes et ordonnés démontables, propriété de laclique fixe (1988), Preprint [8] Brandstädt, A., Classes of bipartite graphs related to chordal graphs, Discrete Appl. Math., 32, 51-60 (1991) · Zbl 0763.05052 [9] Hedetniemi, S.; Laskar, R., A bipartite theory of graphs I, Congr. Numer., 55, 5-14 (1986) [10] Hell, P., Rétractions de graphes, (Ph.D. thesis (1972), Université de Montréal: Université de Montréal Qué) [11] Hell, P., Absolute retracts in graphs, (Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Mathematics, 406 (1973), Springer: Springer Berlin), 291-301 [12] Hell, P., Absolute planar retracts and the four colour conjecture, J. Combin. Theory, 17, 5-10 (1974) · Zbl 0267.05102 [13] Hell, P., Graph retractions, Atti Convegni Lincei Roma, 17, 263-268 (1976) · Zbl 0362.05072 [14] Hell, P.; Rival, I., Absolute retracts and varieties of reflexive graphs, Canad. J. Math., 930, 544-567 (1987) · Zbl 0627.05039 [15] Jawhari, E. M.; Misane, D.; Pouzet, M., Retracts: graphs and ordered sets from the metric point of view, (Combinatorics and Ordered Sets. Combinatorics and Ordered Sets, Contemporary Mathematics, 57 (1986), American Mathematical Society: American Mathematical Society Providence, RI), 175-226 [16] Nowakowski, R.; Rival, I., The smallest graph variety containing all paths, Discrete Math., 43, 223-234 (1983) · Zbl 0511.05059 [17] Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058 [18] Pesch, E., Retracts of Graphs (1988), Athenaeum Verlag: Athenaeum Verlag Frankfurt · Zbl 0667.05021 [19] Quilliot, A., Homomorphismes, points fixes, rétractions et jeux de poursuite dans les graphes, les ensembles ordonnés et les espaces métriques, (Thèse d’Etat, VI (1983), Université de Paris) [20] Winkler, P., The metric structure of graphs - theory and applications, (Whitehead, C., Surveys in Combinatorics 1987. Surveys in Combinatorics 1987, London Mathematical Society Lecture Note Series, 123 (1987), Cambridge University Press: Cambridge University Press Cambridge), 197-221 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.