Hoàng-Reed conjecture holds for tournaments

Frédéric Havet; Stéphan Thomassé; Anders Yeo

doi:10.1016/j.disc.2007.06.033

Hoàng-Reed conjecture holds for tournaments

Frédéric Havet
, Stéphan Thomassé
, Anders Yeo

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

2 Citations (Scopus)

Abstract

Hoàng-Reed conjecture asserts that every digraph D has a collection C of circuits C₁, ..., C_δ+, where δ⁺ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, | V (C_i) ∩ (V (C₁) ∪ ⋯ ∪ V (C_{i - 1})) | ≤ 1, for all i = 2, ..., δ⁺. We verify this conjecture for the class of tournaments.

Original language	English
Pages (from-to)	3412-3415
Number of pages	4
Journal	Discrete Mathematics
Volume	308
Issue number	15
DOIs	https://doi.org/10.1016/j.disc.2007.06.033
Publication status	Published - 6 Aug 2008
Externally published	Yes

Keywords

Tournament
Triangle structure

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.06.033

Cite this

@article{81c536a745ac4badba72b40ef10acfb6,

title = "Ho{\`a}ng-Reed conjecture holds for tournaments",

abstract = "Ho{\`a}ng-Reed conjecture asserts that every digraph D has a collection C of circuits C1, ..., Cδ+, where δ+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, | V (Ci) ∩ (V (C1) ∪ ⋯ ∪ V (Ci - 1)) | ≤ 1, for all i = 2, ..., δ+. We verify this conjecture for the class of tournaments.",

keywords = "Tournament, Triangle structure",

author = "Fr{\'e}d{\'e}ric Havet and St{\'e}phan Thomass{\'e} and Anders Yeo",

year = "2008",

month = aug,

day = "6",

doi = "10.1016/j.disc.2007.06.033",

language = "English",

volume = "308",

pages = "3412--3415",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "15",

}

TY - JOUR

T1 - Hoàng-Reed conjecture holds for tournaments

AU - Havet, Frédéric

AU - Thomassé, Stéphan

AU - Yeo, Anders

PY - 2008/8/6

Y1 - 2008/8/6

N2 - Hoàng-Reed conjecture asserts that every digraph D has a collection C of circuits C1, ..., Cδ+, where δ+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, | V (Ci) ∩ (V (C1) ∪ ⋯ ∪ V (Ci - 1)) | ≤ 1, for all i = 2, ..., δ+. We verify this conjecture for the class of tournaments.

AB - Hoàng-Reed conjecture asserts that every digraph D has a collection C of circuits C1, ..., Cδ+, where δ+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, | V (Ci) ∩ (V (C1) ∪ ⋯ ∪ V (Ci - 1)) | ≤ 1, for all i = 2, ..., δ+. We verify this conjecture for the class of tournaments.

KW - Tournament

KW - Triangle structure

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

U2 - 10.1016/j.disc.2007.06.033

DO - 10.1016/j.disc.2007.06.033

M3 - Article

AN - SCOPUS:43249102657

SN - 0012-365X

VL - 308

SP - 3412

EP - 3415

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 15

ER -

Hoàng-Reed conjecture holds for tournaments

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this