Retracts of Products of Chordal Graphs
Boštjan Brešar, Jérémie Chalopin, Victor D. Chepoi, Matjaž Kovše, Arnaud Labourel, Yann Vaxès · Journal of Graph Theory · 2012
In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K2, 3, the 4-wheel minus one spoke , and the k-wheels (for as induced subgraphs. We also show that these graphs G are exactly the cage-amalgamation graphs as introduced by Brešar and Tepeh Horvat (Cage-amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071–1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 161–180, 2013