Variations on the Gallai-Milgram theorem
type: Item
instance of: scholarly article
title: Variations on the Gallai-Milgram theorem
zbMATH Open document ID: 0661.05028
DOI: 10.1016/0012-365X(88)90063-5
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: The author strengthens the Gallai-Milgram theorem for digraphs \(D\) with independence number two: ``Let \(x\) be a vertex in \(D\) such that for any vertex \(y\neq x\), there exists a path in \(D\) from \(x\) to \(y\); then \(D\) is spanned by two disjoint paths such that \(x\) is the initial vertex of one of them.'' He proposes various problems and conjectures strengthening the Gallai-Milgram theorem and the Gallai-Roy theorem for strong digraphs.
reviewed by: Guy Chaty
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4079451
zbMATH Keywords: chromatic number
zbMATH Keywords: path partition
zbMATH Keywords: independence number
author: Irith Ben-Arroyo Hartman
MaRDI profile type: Publication
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: Q5422499
cites work: Q3267901
cites work: Every finite strongly connected digraph of stability 2 has a Hamiltonian path
cites work: A note on Hamiltonian circuits
cites work: Q5545303
cites work: Q3283482
cites work: A Chvátal-Erdős condition for (1,1)-factors in digraphs
cites work: Q4756732
cites work: Nombre chromatique et plus longs chemins d'un graphe
description: scientific article; zbMATH DE number 4079451