A note concerning paths and independence number in digraphs
type: Item
instance of: scholarly article
title: A note concerning paths and independence number in digraphs
zbMATH Open document ID: 0701.05020
DOI: 10.1016/0012-365X(90)90210-9
author: Geňa Hahn
author: Bill Jackson
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: The authors show that there exist digraphs D such that for all paths \(P_ 1\) and \(P_ 2\) we \(\alpha (D\setminus (P_ 1\cup P_ 2))=\alpha (D)\) They believe that \(f(k)=k(f(k))\) is the smallest integer such that if D is any digraph with \(\alpha (D)=k\) then D contains f(k) paths \(P_ i\) such that \(\alpha (D\setminus \cup_{i=1}^{f(k)}P_ i)<\alpha (D))\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4148114
zbMATH Keywords: path covering
zbMATH Keywords: independence number
zbMATH Keywords: digraphs
reviewed by: Guy Chaty
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Graph Theory and Probability. II
cites work: Q3283482
cites work: A note on the independence number of triangle-free graphs
cites work: Asymptotic lower bounds for Ramsey functions
full work available at URL: 0012-365x(90)90210-9
OpenAlex ID: W2013194273
description: scientific article; zbMATH DE number 4148114