Approximate graph coloring by semidefinite programming
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Combinatorial optimization in system configuration design
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Semidefinite programming in combinatorial optimization
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Approximating the independence number via the -function
- Laplacian eigenvalues and fixed size multisection
- Semidefinite programming
- Heuristics for semirandom graph problems
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- Deciding \(k\)-colorability in expected polynomial time
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- The geometry of graphs and some of its algorithmic applications
- Coloring the normalized Laplacian for oriented hypergraphs
- A unified construction of semiring-homomorphic graph invariants
- More tales of Hoffman: bounds for the vector chromatic number of a graph
- Graph coloring and semidefinite rank
- An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
- Vector coloring the categorical product of graphs
- An SDP primal-dual algorithm for approximating the Lovász-theta function
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- On fractional cut covers
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Spectral lower bounds for the quantum chromatic number of a graph
- Complexity of approximating bounded variants of optimization problems
- Universal completability, least eigenvalue frameworks, and vector colorings
- Graph homomorphisms via vector colorings
- On the adaptable chromatic number of graphs
- Chromatic Gallai identities operating on Lovász number
- A semidefinite programming-based heuristic for graph coloring
- Graph coloring in the estimation of sparse derivative matrices: Instances and applications
- On the probabilistic minimum coloring and minimum k-coloring
- Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
- Quantum homomorphisms
- Shannon capacity and the categorical product
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Total coloring and total matching: polyhedra and facets
- Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
- Semi-definite positive programming relaxations for graph K_n-coloring in frequency assignment.
- Convex relaxations and integrality gaps
- Computational approaches to MAX-cut
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Grothendieck-type inequalities in combinatorial optimization
- Matrix relaxations in combinatorial optimization
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
- An efficient semidefinite programming relaxation for the graph partition problem
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Vertex cover in graphs with locally few colors
- Balanced coloring of bipartite graphs
- A note on the approximation ratio of graph-coloring
- New tools for graph coloring
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- Cubical coloring -- fractional covering by cuts and semidefinite programming
- New heuristics for the vertex coloring problem based on semidefinite programming
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- An approximate algorithm for the (k,d)-coloring problem
- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
- The Operator \Psi for the Chromatic Number of a Graph
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Improving the performance guarantee for approximate graph coloring
- scientific article; zbMATH DE number 4091188 (Why is no real title available?)
- Constructing uniquely realizable graphs
- New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
- scientific article; zbMATH DE number 1256751 (Why is no real title available?)
- New approximation algorithms for graph coloring
- Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Cone-LP's and semidefinite programs: geometry and a simplex-type method
- Coloring bipartite hypergraphs
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- Regular inference as vertex coloring
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- scientific article; zbMATH DE number 2086377 (Why is no real title available?)
- scientific article; zbMATH DE number 2119717 (Why is no real title available?)
- Approximation Algorithms for CSPs
- On minrank and the Lovász theta-function
- Price of anarchy for graph coloring games with concave payoff
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Sampling Strategies for Fast Updating of Gaussian Markov Random Fields
- Approximating the orthogonality dimension of graphs and hypergraphs
- The approximability of assortment optimization under ranking preferences
- Hardness of rainbow coloring hypergraphs
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- An axiomatic duality framework for the theta body and related convex corners
- A notion of total dual integrality for convex, semidefinite, and extended formulations
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Linear index coding via semidefinite programming
- Graphs with Large Girth Not Embeddable in the Sphere
- Communication Lower Bounds Via the Chromatic Number
- MAX k‐CUT and approximating the chromatic number of random graphs
- A class of semidefinite programs with rank-one solutions
- The entropy rounding method in approximation algorithms
- Linear index coding via semidefinite programming
- List-coloring graphs without subdivisions and without immersions
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)
