On certain polytopes associated with graphs

From MaRDI portal

Publication:1393418

Jump to:navigation, search

DOI10.1016/0095-8956(75)90041-6zbMath0277.05139OpenAlexW2058408846WikidataQ59699143 ScholiaQ59699143MaRDI QIDQ1393418

Václav Chvátal

Publication date: 1975

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(75)90041-6

Mathematics Subject Classification ID

Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Polytopes and polyhedra (52Bxx)

Related Items

Decomposition of Directed Graphs, Adjacency on the Postman Polyhedron, Simplex pivots on the set packing polytope, Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles, Persistency of Linear Programming Relaxations for the Stable Set Problem, Partial Permutation and Alternating Sign Matrix Polytopes, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, On perfect graphs and polyhedra with (0, 1)-valued extreme points, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, $t$-Perfection in $P_5$-Free Graphs, The interval order polytope of a digraph, Separation problems for the stable set polytope, Inapproximability of shortest paths on perfect matching polytopes, A Sum of Squares Characterization of Perfect Graphs, Perfectly contractile graphs and quadratic toric rings, A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements, Nearly Gorenstein polytopes, Torsionfreeness for divisor class groups of toric rings of integral polytopes, Birkhoff--von Neumann Graphs that are PM-Compact, Vertex packings: Structural properties and algorithms, Deriving compact extended formulations via LP-based separation techniques, Approximating Incremental Combinatorial Optimization Problems, On the Circuit Diameter of Some Combinatorial Polytopes, ON THE GORENSTEIN PROPERTY OF THE EHRHART RING OF THE STABLE SET POLYTOPE OF AN H-PERFECT GRAPH, Deriving compact extended formulations via LP-based separation techniques, STRONG KOSZULNESS OF TORIC RINGS ASSOCIATED WITH STABLE SET POLYTOPES OF TRIVIALLY PERFECT GRAPHS, Further facet generating procedures for vertex packing polytopes, New facets for the set packing polytope, Adjacency on polymatroids, Unnamed Item, Graph substitution and set packing polytopes, Perfect, ideal and balanced matrices, Line perfect graphs, Discrete relaxations of combinatorial programs, The adjacency relation on the traveling salesman polytope is NP-Complete, On minimal forbidden subgraph characterizations of balanced graphs, Poset entropy versus number of linear extensions: the width-2 case., A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant, Extended formulations from communication protocols in output-efficient time, Existence of unimodular triangulations — positive results, Norms and perfect graphs, On minimal forbidden subgraph characterizations of balanced graphs, Unnamed Item, Unnamed Item, Unnamed Item, Rank of maximum matchings in a graph, A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs, Some facets of the simple plant location polytope, On strongly circular-perfectness, On determining the imperfection ratio, Properties of vertex packing and independence system polyhedra, Perfect zero–one matrices, Two poset polytopes, Relaxations of vertex packing, A solvable case of quadratic 0-1 programming, Polyhedral consequences of the amalgam operation, Near-perfect matrices, Polyhedral proof methods in combinatorial optimization, A polyhedral investigation of star colorings, On randomized stopping points and perfect graphs, A decomposition of 2-weak vertex-packing polytopes, Vertex packing problem application to the design of electronic testing fixtures, Characterizing consistency in probabilistic logic for a class of Horn clauses, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, The weakly connected independent set polytope in corona and join of graphs, On infinite perfect graphs and randomized stopping points on the plane, Edge-colouring of joins of regular graphs. I, Matrices with the Edmonds-Johnson property, On perfect \(0,\pm 1\) matrices, A construction for non-rank facets of stable set polytopes of webs, Recognizing max-flow min-cut path matrices, On the stable set polytope of a series-parallel graph, The complexity of facets resolved, On decomposability of multilinear sets, Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture, Pancyclic properties of the graph of some 0-1 polyhedra, Universally signable graphs, Chair-free Berge graphs are perfect, Total dual integrality and integer polyhedra, On the 0,1 facets of the set covering polytope, A generalization of antiwebs to independence systems and their canonical facets, The Boolean quadratic polytope: Some characteristics, facets and relatives, On the facial structure of the set covering polytope, On cutting-plane proofs in combinatorial optimization, Computing clique and chromatic number of circular-perfect graphs in polynomial time, Perfect graphs are kernel solvable, Graphical properties related to minimal imperfection, The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect, On the X-join decomposition for undirected graphs, Simple extensions of polytopes, Rank inequalities and separation algorithms for packing designs and sparse triple systems., Entropy of symmetric graphs, The stable set polytope of icosahedral graphs, On the perfect matching graph defined by a set of cycles, Hamiltonicity and combinatorial polyhedra, Polytope des independants d'un graphe série-parallèle, On the behavior of the \(N_{+}\)-operator under blocker duality, Discrete extremal problems, On claw-free \(t\)-perfect graphs, On the facets of the stable set polytope of quasi-line graphs, Adjacent vertices on the b-matching polyhedron, Clique family inequalities for the stable set polytope of quasi-line graphs., A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs, Partitive hypergraphs, Coloring planar Toeplitz graphs and the stable set polytope., Fair cost allocations under conflicts - a game-theoretic point of view -, Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs, The complexity of recognizing linear systems with certain integrality properties, On the use of augmenting chains in chain packings, Perfect graphs and norms, The maximum \(k\)-colorable subgraph problem and orbitopes, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Clique-circulants and the stable set polytope of fuzzy circular interval graphs, Adjacency of the 0-1 knapsack problem, Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, Composition of stable set polyhedra, On a graph partition problem with application to VLSI layout, The anti-join composition and polyhedra, Testing balancedness and perfection of linear matrices, A polyhedral approach to the stability of a family of coalitions, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, The nonidealness index of rank-ideal matrices, A min-max relation for stable sets in graphs with no odd-\(K_ 4\), A characterization of cycle-forced bipartite graphs, Matroidal graphs, On the enumeration of certain weighted graphs, The stable set polytope for some extensions of \(P_4\)-free graphs, Vertex adjacencies in the set covering polyhedron, Constructions for normal graphs and some consequences, Gear composition and the stable set polytope, On a theorem of Sewell and Trotter, The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect, Weighted graphs defining facets: A connection between stable set and linear ordering polytopes, Extended formulations, nonnegative factorizations, and randomized communication protocols, Stable sets and graphs with no even holes, On the set covering polyhedron of circulant matrices, Minimum entropy coloring, Characterizing and bounding the imperfection ratio for some classes of graphs, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Adjacency on the constrained assignment problem, The graph of perfect matching polytope and an extreme problem, Odd-\(K_{4}\)'s in stability critical graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, A note on node packing polytopes on hypergraphs, The complexity of facets (and some facets of complexity), Stable sets and polynomials, The maximum clique problem, Entropy splitting for antiblocking corners and perfect graphs, \(K_ i\)-covers. I: Complexity and polytopes, Light on the infinite group relaxation. I: Foundations and taxonomy, The projected faces property and polyhedral relations, On the Chvátal-rank of Antiwebs, Clique and chromatic number of circular-perfect graphs, Integer round-up property for the chromatic number of some \(h\)-perfect graphs, The facets and the symmetries of the approval-voting polytope, Comparing Imperfection Ratio and Imperfection Index for Graph Classes, Circuits and circulant minors, Lift-and-project ranks and antiblocker duality, Three families of toric rings arising from posets or graphs with small class groups, The story of perfectly orderable graphs, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Note on a conjecture of Toft, On low-dimensional faces that high-dimensional polytopes must have, Combinatorial differential algebra of \(x^p\), Stability critical graphs and ranks facets of the stable set polytope, Clique-perfectness and balancedness of some graph classes, Applying Lehman's theorems to packing problems, Bounds on the number of 2-level polytopes, cones, and configurations, The stable set problem: clique and nodal inequalities revisited, Ideal polytopes and face structures of some combinatorial optimization problems, Minimal imperfect graphs: A simple approach, On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure, Complementation in T-perfect graphs, On some graph classes related to perfect graphs: a survey, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, On the combinatorics of the 2-class classification problem, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Perfect graphs, kernels, and cores of cooperative games, Balanced matrices, Characterizing N+-perfect line graphs, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, On the Location and p-Median Polytopes, 2-clique-bond of stable set polyhedra, Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, On circular-perfect graphs: a survey, On the Chvátal rank of linear relaxations of the stable set polytope, Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, A note on the Chvátal-rank of clique family inequalities, Enumeration of 2-level polytopes, On a family of \(0/1\)-polytopes with an NP-complete criterion for vertex nonadjacency relation, A smaller extended formulation for the odd cycle inequalities of the stable set polytope, Edge-colouring of regular graphs of large degree, New valid inequalities and facets for the simple plant location problem, Polyhedral studies of vertex coloring problems: the standard formulation, On the mixed set covering, packing and partitioning polytope, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type, On classes of minimal circular-imperfect graphs, Skew partitions in perfect graphs, A model predictive control approach for discrete-time rescheduling in complex central railway station areas, Unnamed Item, Special simplices and Gorenstein toric rings., Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On non-rank facets of stable set polytopes of webs with clique number four, A polyhedral study of the generalized vertex packing problem, Adjacency on the order polytope with applications to the theory of fuzzy measures, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), On \(f\)-domination: polyhedral and algorithmic results, On the commutativity of antiblocker diagrams under lift-and-project operators, Polyhedral results on the stable set problem in graphs containing even or odd pairs, On a connection between facility location and perfect graphs, On a cardinality-constrained transportation problem with market choice, How to recycle your facets, Linear extensions and comparable pairs in partial orders, Computing the clique number of \(a\)-perfect graphs in polynomial time, Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure, Perfectness of clustered graphs, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, New valid inequalities for the fixed-charge and single-node flow polytopes, The enumeration of several classes of hexagonal systems, A lower bound for the job insertion problem., Strengthened clique-family inequalities for the stable set polytope, On the linear extension complexity of stable set polytopes for perfect graphs, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Modular decomposition of graphs and the distance preserving property, Facets and algorithms for capacitated lot sizing, Z-transformation graphs of perfect matchings of hexagonal systems, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, On Vertices and Facets of Combinatorial 2-Level Polytopes, Two-Level Polytopes with a Prescribed Facet, On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs, Strength of facets for the set covering and set packing polyhedra on circulant matrices, Skeleton matching polytope: realization and isomorphism, A new lifting theorem for vertex packing, Adjacency on combinatorial polyhedra, PM-compact graphs and vertex-deleted subgraphs, Characterising claw-free t-perfect graphs, On the facets of the simple plant location packing polytope, Graph imperfection. I, Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph, On balanced graphs, Almost all webs are not rank-perfect, Stable set rings which are Gorenstein on the punctured spectrum, The simplest families of polytopes associated with NP-hard problems, A characterization of PM-compact Hamiltonian bipartite graphs, Persistency of linear programming relaxations for the stable set problem, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1393418&oldid=13555605"