\(K_ i\)-covers. I: Complexity and polytopes

DOI10.1016/0012-365X(86)90156-1zbMath0584.05052MaRDI QIDQ1070249

Michele Conforti, Derek Gordon Corneil, Ali Ridha Mahjoub

Publication date: 1986

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complete subgraph cover; incidence polytope

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

52Bxx: Polytopes and polyhedra

Related Items

On the 0,1 facets of the set covering polytope, On the facial structure of the set covering polytope, Gallai graphs and anti-Gallai graphs, On a composition of independence systems by circuit identification, The complexity of generalized clique covering, Iterated \(k\)-line graphs, Composition of graphs and the triangle-free subgraph polytope, A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\), Infinite \(\Phi\)-periodic graphs, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on a conjecture by Gavril on clique separable graphs
• Polytope des independants d'un graphe série-parallèle
• Weakly bipartite graphs and the max-cut problem
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• On the symmetric travelling salesman problem I: Inequalities
• Facets of the Bipartite Subgraph Polytope
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• Multi-Terminal Network Flows
• Edge-Deletion Problems
• Set Partitioning: A survey
• Algorithmic Aspects of Vertex Elimination on Graphs
• On the cut polytope
• On the facial structure of set packing polyhedra
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph