Tournament minors

Ilhee Kim; Paul Seymour

doi:10.1016/j.jctb.2014.12.005

Tournament minors

Ilhee Kim, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

21 Scopus citations

Abstract

We say a digraph G is a minor of a digraph H if G can be obtained from a subdigraph of H by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show that the class of all tournaments is a well-quasi-order under minor containment.

Original language	English (US)
Pages (from-to)	138-153
Number of pages	16
Journal	Journal of Combinatorial Theory. Series B
Volume	112
DOIs	https://doi.org/10.1016/j.jctb.2014.12.005
State	Published - May 1 2015

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Digraph
Minor
Tournament
Well-quasi-order

Access to Document

10.1016/j.jctb.2014.12.005

Cite this

@article{31d5adc30fb14ac88efa7ba5f3457191,

title = "Tournament minors",

abstract = "We say a digraph G is a minor of a digraph H if G can be obtained from a subdigraph of H by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show that the class of all tournaments is a well-quasi-order under minor containment.",

keywords = "Digraph, Minor, Tournament, Well-quasi-order",

author = "Ilhee Kim and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier Inc..",

year = "2015",

month = may,

day = "1",

doi = "10.1016/j.jctb.2014.12.005",

language = "English (US)",

volume = "112",

pages = "138--153",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Tournament minors

AU - Kim, Ilhee

AU - Seymour, Paul

PY - 2015/5/1

Y1 - 2015/5/1

N2 - We say a digraph G is a minor of a digraph H if G can be obtained from a subdigraph of H by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show that the class of all tournaments is a well-quasi-order under minor containment.

AB - We say a digraph G is a minor of a digraph H if G can be obtained from a subdigraph of H by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show that the class of all tournaments is a well-quasi-order under minor containment.

KW - Digraph

KW - Minor

KW - Tournament

KW - Well-quasi-order

UR - http://www.scopus.com/inward/record.url?scp=84925039574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925039574&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2014.12.005

DO - 10.1016/j.jctb.2014.12.005

M3 - Article

AN - SCOPUS:84925039574

SN - 0095-8956

VL - 112

SP - 138

EP - 153

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Tournament minors

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this