The Complexity of Near-Optimal Graph Coloring

Cited In (70)

Title not available (Why is that?)
Deciding 3-colourability in less than O(1.415n) steps
On percolation and ‐hardness
CLAP: A New Algorithm for Promise CSPs
Topology and Adjunction in Promise Constraint Satisfaction
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
Local optimization of colorings of graphs
Title not available (Why is that?)
Small Promise CSPs that reduce to large CSPs
Well-quasi-ordering and Embeddability of Relational Structures
Approximate graph colouring and the hollow shadow
Complexity of Coloring Random Graphs
An approximation algorithm for 3-Colourability
Title not available (Why is that?)
Average-case complexity of backtrack search for coloring sparse random graphs
Extremal problems concerning Kneser-graphs
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
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
Near-linear convergence of the random Osborne algorithm for matrix balancing
Structure preserving reductions among convex optimization problems
Graph theory (algorithmic, algebraic, and metric problems)
Randomly colouring graphs (a combinatorial view)
Non-approximability of just-in-time scheduling
Graph Coloring Using Eigenvalue Decomposition
How well can a graph be n-colored?
Discrete extremal problems
A supernodal formulation of vertex colouring with applications in course timetabling
Quantum annealing of the graph coloring problem
Distributed algorithms for maximum cliques
Orthogonal representations over finite fields and the chromatic number of graphs
Worst-case analysis of a new heuristic for the travelling salesman problem
On the triangle clique cover and \(K_t\) clique cover problems
Title not available (Why is that?)
A graph coloring algorithm for large scale scheduling problems
Embedding a novel objective function in a two-phased local search for robust vertex coloring
A better performance guarantee for approximate graph coloring
The smallest hard-to-color graph
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
On the chromatic number of graphs
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
The multichromatic numbers of some Kneser graphs
Coloring k-colorable graphs in constant expected parallel time
On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
Approximation algorithm for maximum edge coloring
On the computational complexity of centers locating in a graph
A note on the complexity of the chromatic number problem
Verifying nonrigidity
Applications of edge coverings by cliques
Maximum bipartite subgraphs of Kneser graphs
Coloration de graphes : fondements et applications
Coloring graph products---a survey

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)