Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers
type: Item
instance of: scholarly article
title: Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers
zbMATH Open document ID: 0928.05030
DOI: 10.1016/S0012-365X(98)00209-X
author: Wenan Zang
published in: Discrete Mathematics
publication date: 2000-01-09T00:00:00Z
review text: A acyclic digraph \(G\) is said to have the Gallai-Milgram-Linial property for clique covers if for every induced subgraph \(H\) and every clique cover of vertices of \(H\) with sink-set \(S\), there is a vertex cover of \(H\) by \(c\) cliques whose sinks come from \(S\), where \(c\) is the largest number of pairwise nonadjacent vertices in \(G\). The author gives the necessary and sufficient conditions that acyclic digraphs have the Gallai-Milgram-Linial property. Five forbidden subgraphs are presented to establish the results.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1321801
zbMATH Keywords: acyclic digraph
zbMATH Keywords: clique covers
zbMATH Keywords: vertex cover
zbMATH Keywords: Gallai-Milgram-Linial property
zbMATH Keywords: forbidden subgraphs
reviewed by: David P. Brown
MaRDI profile type: Publication
cites work: On Greene-Kleitman's theorem for general digraphs
cites work: Q3286847
cites work: An algorithmic note on the gallai-milgram theorem
cites work: Q3347930
cites work: A decomposition theorem for partially ordered sets
cites work: Q3283482
cites work: The structure of Sperner k-families
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Covering digraphs by paths
cites work: Extending the Greene-Kleitman theorem to directed graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Some sequences associated with combinatorial structures
full work available at URL: s0012-365x(98)00209-x
OpenAlex ID: W2062222767
Recommended article: Q4519730
Recommended article: Q3783328
Recommended article: Acyclic graphoidal covers and path partitions in a graph
Recommended article: Q5294935
Recommended article: Clique coverings and partitions of line graphs
Recommended article: Clique covering and clique partition in generalizations of line graphs
Recommended article: On a property of cyclic covers ofp-graphs
Recommended article: Q4030553
Recommended article: Covering Pairs in Directed Acyclic Graphs
Recommended article: Q4014438
description: scientific article; zbMATH DE number 1321801