Longest path partitions in generalizations of tournaments

Jørgen Bang-Jensen; Morten Hegner Nielsen; Anders Yeo

doi:10.1016/j.disc.2006.03.063

Longest path partitions in generalizations of tournaments

Jørgen Bang-Jensen
, Morten Hegner Nielsen
, Anders Yeo

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

24 Citations (Scopus)

Abstract

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ₁, λ₂, such that λ₁ + λ₂ equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D₁ and D₂, such that the order of a longest path in D_i is at most λ_i, for i = 1, 2. We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.

Original language	English
Pages (from-to)	1830-1839
Number of pages	10
Journal	Discrete Mathematics
Volume	306
Issue number	16
DOIs	https://doi.org/10.1016/j.disc.2006.03.063
Publication status	Published - 28 Aug 2006
Externally published	Yes

Keywords

Extended semicomplete digraph
Locally in-semicomplete digraph
Longest path
Path partition conjecture
Quasi-transitive digraph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.03.063

Cite this

@article{622dfd12835a4b44a8d1a5ec691ba70e,

title = "Longest path partitions in generalizations of tournaments",

abstract = "We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ1, λ2, such that λ1 + λ2 equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D1 and D2, such that the order of a longest path in Di is at most λi, for i = 1, 2. We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.",

keywords = "Extended semicomplete digraph, Locally in-semicomplete digraph, Longest path, Path partition conjecture, Quasi-transitive digraph",

author = "J{\o}rgen Bang-Jensen and Nielsen, \{Morten Hegner\} and Anders Yeo",

year = "2006",

month = aug,

day = "28",

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

language = "English",

volume = "306",

pages = "1830--1839",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "16",

}

TY - JOUR

T1 - Longest path partitions in generalizations of tournaments

AU - Bang-Jensen, Jørgen

AU - Nielsen, Morten Hegner

AU - Yeo, Anders

PY - 2006/8/28

Y1 - 2006/8/28

N2 - We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ1, λ2, such that λ1 + λ2 equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D1 and D2, such that the order of a longest path in Di is at most λi, for i = 1, 2. We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.

AB - We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ1, λ2, such that λ1 + λ2 equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D1 and D2, such that the order of a longest path in Di is at most λi, for i = 1, 2. We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.

KW - Extended semicomplete digraph

KW - Locally in-semicomplete digraph

KW - Longest path

KW - Path partition conjecture

KW - Quasi-transitive digraph

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

U2 - 10.1016/j.disc.2006.03.063

DO - 10.1016/j.disc.2006.03.063

M3 - Article

AN - SCOPUS:33746763483

SN - 0012-365X

VL - 306

SP - 1830

EP - 1839

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 16

ER -

Longest path partitions in generalizations of tournaments

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this