Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers
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.
scientific article; zbMATH DE number 1321801
scientific article