Some results and problems on tournament structure

Tung Nguyen; Alex Scott; Paul Seymour

doi:10.1016/j.jctb.2025.02.002

Some results and problems on tournament structure

Tung Nguyen
, Alex Scott
, Paul Seymour

Mathematics

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

2 Scopus citations

Abstract

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.

Original language	English (US)
Pages (from-to)	146-183
Number of pages	38
Journal	Journal of Combinatorial Theory. Series B
Volume	173
DOIs	https://doi.org/10.1016/j.jctb.2025.02.002
State	Published - Jul 2025

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Domination
Tournament colouring
Tournaments

Access to Document

10.1016/j.jctb.2025.02.002

Cite this

@article{4d9ba7cda9984a2599af85179654ecbe,

title = "Some results and problems on tournament structure",

abstract = "This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.",

keywords = "Domination, Tournament colouring, Tournaments",

author = "Tung Nguyen and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2025",

year = "2025",

month = jul,

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

language = "English (US)",

volume = "173",

pages = "146--183",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Some results and problems on tournament structure

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

PY - 2025/7

Y1 - 2025/7

N2 - This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.

AB - This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vertex-disjoint subtournaments A,B, both with large chromatic number, such that all edges between them are directed from A to B? We describe what we know about this question, and report some progress on several other related questions, on tournament colouring and domination.

KW - Domination

KW - Tournament colouring

KW - Tournaments

UR - https://www.scopus.com/pages/publications/85218884189

UR - https://www.scopus.com/pages/publications/85218884189#tab=citedBy

U2 - 10.1016/j.jctb.2025.02.002

DO - 10.1016/j.jctb.2025.02.002

M3 - Article

AN - SCOPUS:85218884189

SN - 0095-8956

VL - 173

SP - 146

EP - 183

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Some results and problems on tournament structure

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this