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

DOI10.4230/LIPICS.STACS.2014.458zbMATH Open1359.05123OpenAlexW2103935895MaRDI QIDQ2965508FDOQ2965508

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

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

zbMATH Keywords

approximation algorithmsgraph coloring

Mathematics Subject Classification ID

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

Cited In (8)

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