### Abstract

We describe how to color every 3-colorable graph with O(n ^{0.2111}) colors, thus improving an algorithm of Blum and Karger from almost a decade ago. Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao, and Vazirani on SPARSEST CUT, and these ideas show promise of leading to further improvements.

Original language | English (US) |
---|---|

Title of host publication | STOC'06 |

Subtitle of host publication | Proceedings of the 38th Annual ACM Symposium on Theory of Computing |

Pages | 215-224 |

Number of pages | 10 |

State | Published - Sep 5 2006 |

Event | 38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 2006 |

ISSN (Print) | 0737-8017 |

### Other

Other | 38th Annual ACM Symposium on Theory of Computing, STOC'06 |
---|---|

Country | United States |

City | Seattle, WA |

Period | 5/21/06 → 5/23/06 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Approximation algorithms
- Chromatic number
- Graph coloring
- Semidefinite programming

## Fingerprint Dive into the research topics of 'New approximation guarantee for chromatic number'. Together they form a unique fingerprint.

## Cite this

Arora, S., Chlamtac, E., & Charikar, M. (2006). New approximation guarantee for chromatic number. In

*STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing*(pp. 215-224). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006).