Abstract
A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T‐cuts is equal to the cardinality of a minimum T‐join for every even subset T of V(G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour J. Comb. Theory B 49 (1990), 189–222; Proc. London Math. Soc. Ser. (3) 42 (1981), 178–192; Gerards, J. Comb. Theory B 55 (1992), 73–82; Szigeti, (1993).) In this paper we prove a characterization of Seymour graphs which was conjectured by Sebö and implies the results mentioned above.
Original language | English (US) |
---|---|
Pages (from-to) | 357-364 |
Number of pages | 8 |
Journal | Journal of Graph Theory |
Volume | 24 |
Issue number | 4 |
DOIs | |
State | Published - Apr 1997 |
Externally published | Yes |