The Complexity of Near-Optimal Graph Coloring

Cited in

(70)

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

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)