Retracts of Products of Chordal Graphs |
| |
| Authors: | Bo?tjan Bre?ar Jérémie Chalopin Victor Chepoi Matja? Kov?e Arnaud Labourel Yann Vaxès |
| |
| Institution: | 1. FACULTY OF NATURAL SCIENCES AND MATHEMATICS, UNIVERSITY OF MARIBOR, , SI‐2000 MARIBOR, SLOVENIA;2. LIF, AIX‐MARSEILLE UNIVERSITé AND CNRS, FACULTé DES SCIENCES DE LUMINY, , MARSEILLE, FRANCE |
| |
| Abstract: | 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 |
| |
| Keywords: | median graph chordal graph retract Cartesian product CAT(0) cubical complexes |
|
|
