On the strong path partition conjecture of Berge
type: Item
instance of: scholarly article
title: On the strong path partition conjecture of Berge
zbMATH Open document ID: 0783.05067
DOI: 10.1016/0012-365X(93)90341-P
author: Juan-Miguel Gracia
published in: Discrete Mathematics
publication date: 1993-11-01T00:00:00Z
review text: Let \(G\) be a directed graph in which not two cycles have a common vertex and whose longest path contains at least \(k\) \((\geq 1)\) vertices. Consider any partition of the vertices of \(G\) into paths \(P_ 1,\ldots,P_ s\) such that \(\sum^ s_ 1\min \bigl\{ | P_ i |,k \bigr\}\) is as small as possible. The author shows that there exists a set of \(k\) mutually disjoint stable sets of \(G\) such that the number of different sets represented by the vertices on each path \(P_ i\) is \(\min \bigl\{ | P_ i |,k \bigr\}\) for \(1 \leq i \leq s\).
reviewed by: J. W. Moon
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 428014
zbMATH Keywords: path partition
zbMATH Keywords: directed graph
zbMATH Keywords: cycles
zbMATH Keywords: longest path
Wikidata QID: Q122927872
MaRDI profile type: Publication
cites work: Path Partitions in Directed Graphs
cites work: k-optimal partitions of a directed graph
cites work: Q5545303
cites work: Q3283482
cites work: Extending the Greene-Kleitman theorem to directed graphs
cites work: Covering digraphs by paths
cites work: Nombre chromatique et plus longs chemins d'un graphe
cites work: On the Berge's strong path partition conjecture
full work available at URL: 0012-365x(93)90341-p
OpenAlex ID: W2026120709
description: scientific article; zbMATH DE number 428014