ISSN:
1572-9192
Keywords:
matroids
;
strong maps
;
homomorphisms
;
duality
;
Menger's theorem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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 duality if for any graph G either there exists a homomorphism σ : 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 C k denotes the circuit of length k + 1, the pairs (C k , C k + 1) 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1011268025029
Permalink
