The Complexity of Near-Optimal Graph Coloring

Cited in

(87)

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

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)