On the Berge's strong path partition conjecture
type: Item
instance of: scholarly article
title: On the Berge's strong path partition conjecture
zbMATH Open document ID: 0783.05083
DOI: 10.1016/0012-365X(93)90245-O
author: S. Singh
published in: Discrete Mathematics
publication date: 1993-08-30T00:00:00Z
review text: A partition of the vertex set of a graph into paths is called a path partition. By a partial \(k\)-coloring of \(G\), we mean a set of \(k\) mutually disjoint stable sets \(S_ 1,S_ 2,\ldots,S_ k\). A vertex \(x \in S_ i\) is assigned the color \(i\). In a partial \(k\)-coloring a path \(P\) is strongly colored if the number of different colors represented in \(P\) is equal to \(\min \bigl\{ k,| P | \bigr\}\). Let \(k \geq 1\) be an integer. For a path partition \(S=(P_ 1,P_ 2,\ldots,P_ q)\) set \[ B_ k(S)=\sum^{i=q}_{i=1}\min \bigl\{ k,| P_ i | \bigr\}. \] A partition \(S'=(P_ 1,P_ 2,\ldots,P{_ q'})\) is \(k\)-finer then \(S\) if \(B_ k(S')<B_ k(S)\) and \(S'\) is \(k\)-optimal if there is no \(k\)-finer partition than \(S'\). In the present paper the author proved that for every \(k\)-optimal path partition of a digraph in which each component contains at most one cycle, there exists a partial \(k\)-coloring which colors strongly every path of the partition.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 179609
zbMATH Keywords: strong path partition conjecture
zbMATH Keywords: partial \(k\)-coloring
zbMATH Keywords: path partition
zbMATH Keywords: stable sets
zbMATH Keywords: digraph
Wikidata QID: Q123266822
reviewed by: B. Andrasfai
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
description: scientific article; zbMATH DE number 179609