The Complexity of Near-Optimal Graph Coloring

Cited in

(85)

Coloring graph products---a survey
Average-case complexity of backtrack search for coloring sparse random graphs
Extremal problems concerning Kneser-graphs
Approximating the orthogonality dimension of graphs and hypergraphs
Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
Complexity of dimension three and some related edge-covering characteristics of graphs
A note on the approximation of the MAX CLIQUE problem
Finding approximate solutions to NP-hard problems by neural networks is hard
Quantifiers and approximation
scientific article; zbMATH DE number 7561683 (Why is no real title available?)
Quantum advantage and CSP complexity
1-in-3 vs. not-all-equal: dichotomy of a broken promise
Injective hardness condition for PCSPs
Deciding 3-colourability in less than O(1.415n) steps
1-in-3 vs. not-all-equal: dichotomy of a broken promise
Linearly ordered colourings of hypergraphs
Non deterministic polynomial optimization problems and their approximations
On approximating the minimum independent dominating set
Kneser's conjecture, chromatic number, and homotopy
Routing a vehicle of capacity greater than one
The complexity of multicolouring
Optimization, approximation, and complexity classes
NP-completeness of a family of graph-colouring problems
On the complexity of H-coloring
The hardness of approximation: Gap location
Worst-Case Analysis of Network Design Problem Heuristics
Clustering to minimize the maximum intercluster distance
Bidegree of graph and degeneracy number
Structure preserving reductions among convex optimization problems
Graph theory (algorithmic, algebraic, and metric problems)
Near-linear convergence of the random Osborne algorithm for matrix balancing
Complexity of coloring random graphs: an experimental study of the hardest region
Randomly colouring graphs (a combinatorial view)
Non-approximability of just-in-time scheduling
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Solving promise equations over monoids and groups
On the complexity of symmetric vs. functional PCSPs
Computing a 3-role assignment is polynomial-time solvable on complementary prisms
Graph Coloring Using Eigenvalue Decomposition
CLAP: A New Algorithm for Promise CSPs
Topology and Adjunction in Promise Constraint Satisfaction
How well can a graph be n-colored?
Discrete extremal problems
The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
A supernodal formulation of vertex colouring with applications in course timetabling
Beyond PCSP (1-in-3, NAE)
The complexity of promise SAT on non-Boolean domains
Local optimization of colorings of graphs
Quantum annealing of the graph coloring problem
On percolation and \(\mathcal{NP}\)-hardness
Worst-case analysis of a new heuristic for the travelling salesman problem
Orthogonal representations over finite fields and the chromatic number of graphs
scientific article; zbMATH DE number 3683613 (Why is no real title available?)
Distributed algorithms for maximum cliques
A graph coloring algorithm for large scale scheduling problems
On the triangle clique cover and \(K_t\) clique cover problems
Quantum advantage and CSP complexity
Embedding a novel objective function in a two-phased local search for robust vertex coloring
Small Promise CSPs that reduce to large CSPs
The smallest hard-to-color graph
A better performance guarantee for approximate graph coloring
Solving promise equations over monoids and groups
Zero knowledge and the chromatic number
The complexity of some problems related to GRAPH 3-COLORABILITY
On approximation problems related to the independent set and vertex cover problems
Coloring certain proximity graphs
Probabilistically checkable proofs and their consequences for approximation algorithms
On proving that a graph has no large clique: A connection with Ramsey theory
On the chromatic number of graphs
The multichromatic numbers of some Kneser graphs
Well-quasi-ordering and Embeddability of Relational Structures
Approximate graph colouring and the hollow shadow
On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
Coloring k-colorable graphs in constant expected parallel time
Approximation algorithm for maximum edge coloring
A note on the complexity of the chromatic number problem
On the computational complexity of centers locating in a graph
Verifying nonrigidity
Applications of edge coverings by cliques
Approximate graph coloring and the crystal with a hollow shadow
Maximum bipartite subgraphs of Kneser graphs
Semidefinite programming and linear equations vs. homomorphism problems
An approximation algorithm for 3-Colourability
Coloration de graphes : fondements et applications

This page was built for publication: The Complexity of Near-Optimal Graph Coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4083458)