Tension continuous maps—Their structure and applications

We consider mappings between edge sets of graphs that lift tensions to tensions. Such mappings are called tension-continuous mappings (shortly TTTT mappings). The existence of a TTTT mapping induces a (quasi)order on the class of graphs, which seems to be an essential extension of the homomorphism order (studied extensively, see Hell and Nešetřil (2004) [10]). In this paper we study the relationship of the homomorphism and TTTT orders. We stress the similarities and the differences in both deterministic and random settings. Particularly, we prove that TTTT order is universal and investigate graphs for which homomorphisms and TTTT mappings coincide (so-called homotens graphs). In the course of our study, we prove a new Ramsey-type theorem, which may be of independent interest. We solve a problem asked in [Matt DeVos, Jaroslav Nešetřil, André Raspaud, On edge-maps whose inverse preserves flows and tensions, in: J.A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, J.L. Ramirez Alfonsin (Eds.), Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, in: Trends in Mathematics, Birkhäuser, 2006].