Premium
A characterization of Seymour graphs
Author(s) -
Ageev A. A.,
Kostochka A. V.,
Szigeti Z.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199704)24:4<357::aid-jgt8>3.0.co;2-n
Subject(s) - combinatorics , mathematics , discrete mathematics , characterization (materials science) , cardinality (data modeling) , disjoint sets , pathwidth , cograph , chordal graph , graph , 1 planar graph , line graph , computer science , materials science , data mining , nanotechnology
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. © 1997 John Wiley & Sons, Inc.