A Note on Maxflow-Mincut and Homomorphic Equivalence in Matroids
Malostransk · 2000
Graph homomorphisms are used to study good characterizations for coloring problems (Trans. Amer. Math. Soc. 384 (1996), 1281-1297;Discrete Math.22 (1978), 287-300). Particularly, the following concept arises in this context: A pair of graphs . A; B/ is called a homomorphism dualityif for any graph G either there exists a homomorphismae : A! G or there exists a homomorphism? : G! B but not both. In this paper we show that maxflow-mincut duality for matroids can be put into this framework using strong maps as homomorphisms. More precisely, we show that, if Ck denotes the circuit of length kC 1, the pairs.Ck; CkC1/ are the only homomorphism dualities in the class of duals of matroids with the strong integer maxflow-mincut property ( Jour. Comb. Theor. Ser.B 23 (1977), 189-222). Furthermore, we prove that for general matroids there is only a trivial homomorphism duality.