A Characterization of Seymour Graphs

A. A. Ageev, A. V. Kostochka, Z. Szigeti

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)357-364
Number of pages8
JournalJournal of Graph Theory
Issue number4
StatePublished - Apr 1997
Externally publishedYes

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'A Characterization of Seymour Graphs'. Together they form a unique fingerprint.

Cite this