A characterization of seymour graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [5][6], Gerards [1], Szigeti [7]). In this paper we prove a characterization of Seymour graphs which was conjectured by Seb6 and implies the results mentioned above.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 4th International IPCO Conference, 1995, Proceedings
EditorsEgon Balas, Jens Clausen
PublisherSpringer
Pages364-372
Number of pages9
ISBN (Print)9783540594086
DOIs
StatePublished - 1995
Externally publishedYes
Event4th International Conference on Integer Programming and Combinatorial Optimization, IPCO 1995 - Copenhagen, Denmark
Duration: May 29 1995May 31 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume920
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Conference on Integer Programming and Combinatorial Optimization, IPCO 1995
Country/TerritoryDenmark
CityCopenhagen
Period5/29/955/31/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A characterization of seymour graphs'. Together they form a unique fingerprint.

Cite this