\(K_ i\)-covers. I: Complexity and polytopes
type: Item
instance of: scholarly article
title: \(K_ i\)-covers. I: Complexity and polytopes
zbMATH Open document ID: 0584.05052
DOI: 10.1016/0012-365X(86)90156-1
author: Michele Conforti
author: Derek G. Corneil
author: A. R. Mahjoub
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: In a graph \(G\) a \(K_ i\) is a complete subgraph of size i. A \(K_ i\)-cover of \(G\) is a set \(C\) of \(K_{i-1}'s\) of \(G\) such that every \(K_ i\) in \(G\) contains at least one \(K_{i-1}\) from \(C\). It is proved that the problem of determining whether a general graph has a \(K_ i\)-cover (i\(\geq 2)\) of cardinality \(\leq k\) is NP-complete. For chordal graphs with fixed maximum clique size, the problem is shown to be polynomial. A partial characterization for the \((K_{i-1}-K_ i)\)-incidence polytope is given by some classes of facets for which the separation problem can be solved in polynomial time.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 52Bxx
zbMATH DE Number: 3935091
zbMATH Keywords: complete subgraph cover
zbMATH Keywords: incidence polytope
reviewed by: Peter Kleinschmidt
MaRDI profile type: Publication
cites work: Set Partitioning: A survey
cites work: Facets of the Bipartite Subgraph Polytope
cites work: On the cut polytope
cites work: Polytope des independants d'un graphe série-parallèle
cites work: On certain polytopes associated with graphs
cites work: A note on a conjecture by Gavril on clique separable graphs
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
cites work: Q3328583
cites work: Multi-Terminal Network Flows
cites work: Q3328286
cites work: On the symmetric travelling salesman problem I: Inequalities
cites work: Weakly bipartite graphs and the max-cut problem
cites work: Q4142699
cites work: On the facial structure of set packing polyhedra
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: A class of facet producing graphs for vertex packing polyhedra
cites work: Edge-Deletion Problems
full work available at URL: 0012-365x(86)90156-1
OpenAlex ID: W1966227787
description: scientific article; zbMATH DE number 3935091