The sandwich theorem
From MaRDI portal
Publication:1344393
zbMath0810.05065arXivmath/9312214MaRDI QIDQ1344393
Publication date: 12 February 1995
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9312214
Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items
New lower bounds for the Shannon capacity of odd cycles, On NP-hardness of the clique partition -- independence number gap recognition and related problems, Conic formulations of graph homomorphisms, A heuristic for the stability number of a graph based on convex quadratic programming and tabu search, Copositive programming motivated bounds on the stability and the chromatic numbers, A Derivation of Lovász' Theta via Augmented Lagrange Duality, Copositivity cuts for improving SDP bounds on the clique number, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Information theoretic parameters of noncommutative graphs and convex corners, A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming, Semidefinite programming in combinatorial optimization, Graph coloring and semidefinite rank, Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture, Semidefinite programming relaxations for graph coloring and maximal clique problems, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, Approximating the independence number via the \(\vartheta\)-function, Sabidussi versus Hedetniemi for three variations of the chromatic number, A Bound on the Shannon Capacity via a Linear Programming Variation, On Sidorenko's conjecture for determinants and Gaussian Markov random fields, Semidefinite programming and its applications to NP problems, All normalized anti-monotonic overlap graph measures are bounded, Improving an upper bound on the size of \(k\)-regular induced subgraphs, Duality of graph invariants, Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited, On the flip graphs on perfect matchings of complete graphs and signed reversal graphs, Resource convertibility and ordered commutative monoids, Collective dynamics of phase-repulsive oscillators solves graph coloring problem, Unnamed Item, Orthonormal representations of \(H\)-free graphs, Regular inference as vertex coloring, Spectral bounds for the independence ratio and the chromatic number of an operator, Chromatic Gallai identities operating on Lovász number, Why Is Maximum Clique Often Easy in Practice?, A sequential elimination algorithm for computing bounds on the clique number of a graph, Coloring the normalized Laplacian for oriented hypergraphs, Computing inductive vertex orderings, A new property of the Lovász number and duality relations between graph parameters, An axiomatic duality framework for the theta body and related convex corners, An SDP primal-dual algorithm for approximating the Lovász-theta function, Sandwich theorems and capacity bounds for non-commutative graphs, Semidefinite programming for discrete optimization and matrix completion problems, Quadratic factorization heuristics for copositive programming, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, On linear and semidefinite programming relaxations for hypergraph matching, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Approximability of clique transversal in perfect graphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Invariant Semidefinite Programs, A unified construction of semiring-homomorphic graph invariants, Exact bounds on the order of the maximum clique of a graph., The minrank of random graphs over arbitrary fields, A Graph Theoretic Formula for the Number of Primes $\pi(n)$, Probabilistic refinement of the asymptotic spectrum of graphs, Three new upper bounds on the chromatic number, Unnamed Item, The problem of quantum correlations and the totalitarian principle, Orthogonal representations over finite fields and the chromatic number of graphs, Exploiting special structure in semidefinite programming: a survey of theory and applications, Lower bounds for measurable chromatic numbers, Chromatic numbers, Sabidussi's theorem and Hedetniemi's conjecture for non-commutative graphs, Worst-case analysis of clique MIPs, Eigenvalue interlacing and weight parameters of graphs, Spectral characterizations of the Lovász number and the Delsarte number of a graph, Unnamed Item, Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, Clique, chromatic, and Lovász numbers of certain circulant graphs
