Finding Pseudorandom Colorings of Pseudorandom Graphs
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1874447
- Colouring random graphs
- scientific article; zbMATH DE number 4101221
- On pseudocomplete coloring of graphs
- scientific article; zbMATH DE number 1984543
- Colouring Semirandom Graphs
- Randomly colouring graphs (a combinatorial view)
- List coloring of random and pseudo-random graphs
- Coloring Random and Semi-Random k-Colorable Graphs
- Randomly colorable graphs in greedy coloring
Cites work
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate graph coloring by semidefinite programming
- Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
- Coloring Random and Semi-Random k-Colorable Graphs
- Conditional Hardness for Approximate Coloring
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- New approximation guarantee for chromatic number
- New tools for graph coloring
- On the effect of randomness on planted 3-coloring models
- Structure and randomness. Pages from year one of a mathematical blog
- Subexponential algorithms for unique games and related problems
Cited in
(3)
This page was built for publication: Finding Pseudorandom Colorings of Pseudorandom Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136329)
