New approximation algorithms for graph coloring
From MaRDI portal
Recommendations
Cited in
(47)- Combinatorial optimization in system configuration design
- On-line coloring \(k\)-colorable graphs
- Differential approximation algorithms for some combinatorial optimization problems
- Approximation results for the minimum graph coloring problem
- Efficient learning of typical finite automata from random walks
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Polynomial approximation and graph-coloring
- Improving graph colouring algorithms and heuristics using a novel representation
- Three-quarter approximation for the number of unused colors in graph coloring
- New potential functions for greedy independence and coloring
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Convex relaxations and integrality gaps
- An approximate algorithm for the chromatic number of graphs
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- A note on the approximation ratio of graph-coloring
- New tools for graph coloring
- Improved inapproximability results for maximum k-colorable subgraph
- scientific article; zbMATH DE number 3854439 (Why is no real title available?)
- Improving the performance guarantee for approximate graph coloring
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- scientific article; zbMATH DE number 1751952 (Why is no real title available?)
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- Coloring -colorable graphs using relatively small palettes
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- On the hardness of approximating the minimum consistent OBDD problem
- Approximating the orthogonality dimension of graphs and hypergraphs
- Hardness of rainbow coloring hypergraphs
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Progress (and lack thereof) for graph coloring approximation problems
- New Algorithm for Chromatic Number of Graphs and their Applications
- Linear index coding via semidefinite programming
- Linear index coding via semidefinite programming
- Approximating the orthogonality dimension of graphs and hypergraphs
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- CLAP: A New Algorithm for Promise CSPs
- Approximating \(k\)-forest with resource augmentation: a primal-dual approach
- An approximation algorithm for 3-Colourability
- Robust Factorizations and Colorings of Tensor Graphs
- Coloring tournaments with few colors: algorithms and complexity
- Cheeger's inequalities for vertex expansion and reweighted eigenvalues
- Linearly ordered colourings of hypergraphs
- Improved linearly ordered colorings of hypergraphs via SDP rounding
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Report 7/2006: Algorithmic Graph Theory (February 12th -- February 18th, 2006)
- A better performance guarantee for approximate graph coloring
- A simple algorithm for 4-coloring 3-colorable planar graphs
This page was built for publication: New approximation algorithms for graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4305670)
