2005/03/17 by Jaroslav Nesetril, Nesetril, Jaroslav, Robert Samal +1 · 1 citation
Mathematics · #05C15 #05C25 #05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C25 #msc:05C38
paper · pdf · doi:10.48550/arxiv.math/0503360
32 pages
arxiv created 2005/03/17 · arxiv updated 2009/12/01
We consider mappings between edge sets of graphs that lift tensions to tensions. Such mappings are called tension-continuous mappings (shortly TT mappings). Existence of a TT 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-Nesetril]). In this paper we study the relationship of the homomorphism and TT orders. We stress the similarities and the differences in both deterministic and random setting. Particularly, we prove that TT order is dense and universal and we solve a problem of M. DeVos et al.