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

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

Ali Ridha Mahjoub, Derek Gordon Corneil, Michele Conforti

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0012-365x(86)90156-1

zbMATH Keywords

complete subgraph coverincidence polytope

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polytopes and polyhedra (52Bxx)

Related Items

Iterated \(k\)-line graphs, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\), Infinite \(\Phi\)-periodic graphs, A semidefinite approach to the $K_i$-cover problem, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, 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, Triangle packings and transversals of some \(K_{4}\)-free graphs, Generalized line graphs: Cartesian products and complexity of recognition, On a composition of independence systems by circuit identification, The complexity of generalized clique covering, Composition of graphs and the triangle-free subgraph polytope

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