Geodesic
A note on maxflow-mincut and homomorphic equivalence in matroids
Journal of Algebraic Combinatorics, Tome 12 (2000) no. 3, pp. 295-300.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 $sgr : ArarrG$ or there exists a homomorphism $tau : GrarrB$ 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.
Keywords: matroids, strong maps, homomorphisms, duality, Menger's theorem 
@article{JAC_2000__12_3_a0,
     author = {Hochst\"attler, Winfried and Ne\v{s}et\v{r}il, Jaroslav},
     title = {A note on maxflow-mincut and homomorphic equivalence in matroids},
     journal = {Journal of Algebraic Combinatorics},
     pages = {295--300},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2000},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2000__12_3_a0/}
}
TY  - JOUR
AU  - Hochstättler, Winfried
AU  - Nešetřil, Jaroslav
TI  - A note on maxflow-mincut and homomorphic equivalence in matroids
JO  - Journal of Algebraic Combinatorics
PY  - 2000
SP  - 295
EP  - 300
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2000__12_3_a0/
LA  - en
ID  - JAC_2000__12_3_a0
ER  - 
%0 Journal Article
%A Hochstättler, Winfried
%A Nešetřil, Jaroslav
%T A note on maxflow-mincut and homomorphic equivalence in matroids
%J Journal of Algebraic Combinatorics
%D 2000
%P 295-300
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2000__12_3_a0/
%G en
%F JAC_2000__12_3_a0
Hochstättler, Winfried; Nešetřil, Jaroslav. A note on maxflow-mincut and homomorphic equivalence in matroids. Journal of Algebraic Combinatorics, Tome 12 (2000) no. 3, pp. 295-300. http://geodesic.mathdoc.fr/item/JAC_2000__12_3_a0/