Bipartitions of Highly Connected Tournaments

Jaehoon Kim; Daniela Kuhn; Deryk Osthus

doi:10.1137/15M1006611

Bipartitions of Highly Connected Tournaments

Jaehoon Kim, Daniela Kuhn, Deryk Osthus

Mathematics

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

4 Citations (Scopus)

142 Downloads (Pure)

Abstract

We show that if T is a strongly 10⁹k⁶ log(2k)-connected tournament, there exists
a partition A;B of V (T) such that each of T[A], T[B] and T[A;B] is strongly k-connected.
This provides solutions to tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs. We also discuss spanning linkages as well as non-separating subdivisions in highly connected tournaments.

Original language	English
Pages (from-to)	895–911
Journal	SIAM Journal on Discrete Mathematics
Volume	30
Issue number	2
Early online date	12 May 2016
DOIs	https://doi.org/10.1137/15M1006611
Publication status	E-pub ahead of print - 12 May 2016

Access to Document

10.1137/15M1006611

accepted author manuscript
Eligibility for repository: Checked on 6/6/2016
Accepted author manuscript, 402 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{e29754dcd6f64a9f95e829e8548a4210,

title = "Bipartitions of Highly Connected Tournaments",

abstract = "We show that if T is a strongly 109k6 log(2k)-connected tournament, there existsa partition A;B of V (T) such that each of T[A], T[B] and T[A;B] is strongly k-connected.This provides solutions to tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs. We also discuss spanning linkages as well as non-separating subdivisions in highly connected tournaments.",

author = "Jaehoon Kim and Daniela Kuhn and Deryk Osthus",

year = "2016",

month = may,

day = "12",

doi = "10.1137/15M1006611",

language = "English",

volume = "30",

pages = "895–911",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Bipartitions of Highly Connected Tournaments

AU - Kim, Jaehoon

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2016/5/12

Y1 - 2016/5/12

N2 - We show that if T is a strongly 109k6 log(2k)-connected tournament, there existsa partition A;B of V (T) such that each of T[A], T[B] and T[A;B] is strongly k-connected.This provides solutions to tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs. We also discuss spanning linkages as well as non-separating subdivisions in highly connected tournaments.

AB - We show that if T is a strongly 109k6 log(2k)-connected tournament, there existsa partition A;B of V (T) such that each of T[A], T[B] and T[A;B] is strongly k-connected.This provides solutions to tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs. We also discuss spanning linkages as well as non-separating subdivisions in highly connected tournaments.

U2 - 10.1137/15M1006611

DO - 10.1137/15M1006611

M3 - Article

SN - 0895-4801

VL - 30

SP - 895

EP - 911

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Bipartitions of Highly Connected Tournaments

Abstract

Access to Document

Fingerprint

Cite this