Stable sets and polynomials
From MaRDI portal
Publication:1313833
DOI10.1016/0012-365X(92)00057-XzbMath0792.05082MaRDI QIDQ1313833
Publication date: 1 March 1994
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items
Clique-stable set separation in perfect graphs with no balanced skew-partitions, A note on the reducedness and Gröbner bases of Specht ideals, Maximum weighted induced subgraphs, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Standard complexes of matroids and lattice paths, Checking strict positivity of Kraus maps is NP-hard, Clique versus independent set, On the stable solution of large scale problems over the doubly nonnegative cone, An algebraic formulation of hypergraph colorings, Algebraic proof systems over formulas., Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases, Low degree Nullstellensatz certificates for 3-colorability, Hermitian matrices with a bounded number of eigenvalues, Decomposition techniques applied to the clique-stable set separation problem, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, INDEPENDENT SETS FROM AN ALGEBRAIC PERSPECTIVE, Handelman's hierarchy for the maximum stable set problem, Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz, Some Combinatorial Applications of Gröbner Bases, Invariant theoretic characterization of subdiscriminants of matrices, A continuous characterization of the maximum vertex-weighted clique in hypergraphs, Algebraic characterization of uniquely vertex colorable graphs, On the complexity of Hilbert refutations for partition, Derivation radical subspace arrangements, Scheduling jobs on identical machines with agreement graph, Nowhere-zero flow polynomials, Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Several notes on the power of Gomory-Chvátal cuts, A note on Turán's theorem, Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares, Complexity of Null- and Positivstellensatz proofs, 2-colorability of \(r\)-uniform hypergraphs, Communication Complexity of Pairs of Graph Families with Applications, A note on greedy algorithms for the maximum weighted independent set problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Independence numbers of graphs and generators of ideals
- The perfectly matchable subgraph polytope of an arbitrary graph
- Relaxations of vertex packing
- Matching theory
- Colorings and orientations of graphs
- Geometric algorithms and combinatorial optimization
- On certain polytopes associated with graphs
- Stability critical graphs and ranks facets of the stable set polytope
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Compositions of Graphs and Polyhedra II: Stable Sets
- A Problem in Graph Theory
- A Theorem on k-Saturated Graphs
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Combinatorics and commutative algebra