Retracts of products of chordal graphs

Boštjan Brešar (Avtor), Jérémie Chalopin (Avtor), Victor Chepoi (Avtor), Matjaž Kovše (Avtor), Arnaud Labourel (Avtor), Yann Vaxès (Avtor)

Povzetek

We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫-wheels ▫$W_k$▫, and ▫$k$▫-wheels minus one spoke T$W_k^- \; (k \ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cage-amalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" 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.

Ključne besede

teorija grafov;graf;retrakt;zastražena amalgamacija;tetiven graf;kartezični produkt grafov;medianski graf;graph theory;graph;retract;gated amalgamation;chordal graph;Cartesian product of graphs;median graph;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	0 - Ni določena
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15751513
ISSN:	2232-2094
Matična publikacija:	Preprint series
Št. ogledov:	37
Št. prenosov:	13
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	teorija grafov;graf;retrakt;zastražena amalgamacija;tetiven graf;kartezični produkt grafov;medianski graf;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-20
Letnik:	Vol. 48
Zvezek:	št. 1134
Čas izdaje:	2010
ID:	1475275