Coloring 3-colorable graphs with o(n^1/5) colors

DOI10.4230/LIPICS.STACS.2014.458MaRDI QIDQ2965508zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Mikkel Thorup

Publication date 3 March 2017

Full work available at URL https://doi.org/10.4230/lipics.stacs.2014.458

zbMATH Keywords

approximation algorithmsgraph coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring -colorable graphs using relatively small palettes
• Coloring \(k\)-colorable graphs using smaller palettes
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Approximate graph coloring by semidefinite programming

Cited in

(8)

• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Deciding 3-colourability in less than O(1.415n) steps
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• New tools for graph coloring
• Robust Factorizations and Colorings of Tensor Graphs
• Distinguishing colorings of 3-connected planar graphs with five colors
• Coloring -colorable graphs using relatively small palettes
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors

This page was built for publication: Coloring 3-colorable graphs with \(o(n^{1/5})\) colors

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