Approximate graph coloring by semidefinite programming
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Convex relaxations and integrality gaps
- Coloring bipartite hypergraphs
- On the probabilistic minimum coloring and minimum k-coloring
- Price of anarchy for graph coloring games with concave payoff
- Hardness of rainbow coloring hypergraphs
- Improved linearly ordered colorings of hypergraphs via SDP rounding
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- A note on the approximation ratio of graph-coloring
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- On the adaptable chromatic number of graphs
- Vector coloring the categorical product of graphs
- On minrank and the Lovász theta-function
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- Universal completability, least eigenvalue frameworks, and vector colorings
- Linear index coding via semidefinite programming
- Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
- An axiomatic duality framework for the theta body and related convex corners
- The Operator \Psi for the Chromatic Number of a Graph
- Semidefinite programming and linear equations vs. homomorphism problems
- List-coloring graphs without subdivisions and without immersions
- Coloring the normalized Laplacian for oriented hypergraphs
- Solving graph equipartition SDPs on an algebraic variety
- On fractional cut covers
- Deciding \(k\)-colorability in expected polynomial time
- A class of semidefinite programs with rank-one solutions
- Constructing uniquely realizable graphs
- Quantum homomorphisms
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Improving the performance guarantee for approximate graph coloring
- Approximating the orthogonality dimension of graphs and hypergraphs
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- Semi-definite programming and quantum information
- New tools for graph coloring
- scientific article; zbMATH DE number 7561683 (Why is no real title available?)
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- More tales of Hoffman: bounds for the vector chromatic number of a graph
- Chromatic Gallai identities operating on Lovász number
- MAX k‐CUT and approximating the chromatic number of random graphs
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Semidefinite programming
- On approximating the longest path in a graph
- Linearly ordered colourings of hypergraphs
- A notion of total dual integrality for convex, semidefinite, and extended formulations
- A simple algorithm for 4-coloring 3-colorable planar graphs
- On the tractability of coloring semirandom graphs
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
- A semidefinite programming-based heuristic for graph coloring
- Cubical coloring -- fractional covering by cuts and semidefinite programming
- An SDP primal-dual algorithm for approximating the Lovász-theta function
- Graph homomorphisms via vector colorings
- Heuristics for semirandom graph problems
- Semi-definite positive programming relaxations for graph K_n-coloring in frequency assignment.
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
- Quadratic forms on graphs
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- An approximate algorithm for the (k,d)-coloring problem
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Computing the partition function for graph homomorphisms
- Graphs with Large Girth Not Embeddable in the Sphere
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
- The approximability of assortment optimization under ranking preferences
- Matrix relaxations in combinatorial optimization
- scientific article; zbMATH DE number 4091188 (Why is no real title available?)
- Linear index coding via semidefinite programming
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Computational approaches to MAX-cut
- Semidefinite programming in combinatorial optimization
- New heuristics for the vertex coloring problem based on semidefinite programming
- Grothendieck-type inequalities in combinatorial optimization
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- The Lovász theta function for random regular graphs and community detection in the hard regime
- The geometry of graphs and some of its algorithmic applications
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- The Lovász number of random graphs
- Copositive programming motivated bounds on the stability and the chromatic numbers
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Regular inference as vertex coloring
- Balanced coloring of bipartite graphs
- Graph coloring and semidefinite rank
- Laplacian eigenvalues and fixed size multisection
- Wireless capacity with arbitrary gain matrix
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Approximation Algorithms for CSPs
- scientific article; zbMATH DE number 2119717 (Why is no real title available?)
- Shannon capacity and the categorical product
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Complexity of approximating bounded variants of optimization problems
- Combinatorial optimization in system configuration design
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- Robust Factorizations and Colorings of Tensor Graphs
- An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
This page was built for publication: Approximate graph coloring by semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3841651)
