Approximate Graph Coloring
This term our reading group studies approximations for the chromatic number of a graph. This topic was suggested by Ben Moore. Thank you Ben for contributing the topic and suggested list of papers!
Ben will also give our first talk, an overview of the area and the first result in Group A, on January 18th.
The suggested papers are available below. If you would like to present one of the unclaimed papers, or suggest a paper to present, please get in touch with one of the organizers.
Group A: Coloring in minor closed classes (these papers require some expertise in graph minors theory)
| Date | Topic | Presenter |
|---|---|---|
| Jan 18th, 2019 | ‘Additive non-approximability of chromatic number in proper minor-closed classes’ by Dvorak and Kawarabayashi. | Ben Moore |
| Jan 25th, 2019 | An additive t+3 approximation of the chromatic number for minor-closed classes that avoid a fixed t-apex graph as a minor. See Theorem 5 from the work of Dvorak and Kawarabayashi mentioned above. | Justin Toth |
| Feb 1st, 2019 | A 2-approximation for the chromatic number in minor closed classes. Based on the work of Demaine, Hajiaghayi, and Kawarabayashi in the paper titled ‘Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring’. | Rose McCarty |
Group B: Coloring in general graphs
| Date | Topic | Presenter |
|---|---|---|
| Feb 8th, 2019 | ‘Coloring 3-colorable graphs with o(n^1⁄5) colors’ by Kawarabayashi and Thorup. First talk covers combinatorial techniques used in this paper. | Thomas Kelly |
| Feb 15th, 2019 | Second talk (on the above paper) covers the semi-definite programming approaches. | Sharat Ibrahimpur |
| Mar 8th, 2019 | ‘On the hardness of 4-coloring a 3-colorable graph’ by Guruswami and Khanna, and ‘On the hardness of approximating the chromatic number’ by Khanna, Linial, and Safra. | Akshay Ramachandran |
Group C: Other interesting results on coloring.
| Date | Topic | Presenter |
|---|---|---|
| Mar 1st, 2019 | Courcelle’s Theorem: Fixed parameter linear problems with respect to tree-width. From ‘The monadic second-order logic of graphs. I. Recognizable sets of finite graphs’ by Bruno Courcelle | Rose McCarty |
| Mar 15th, 2019 | ‘NP-Hardness of Coloring 2-Colorable Hypergraphs with Poly-Logarithmically Many Colors’ by Amey Bhangale. | Joshua Nevin |
| Mar 22nd, 2019 | Structural Rroperties of the Glauber Dynamic Graph | Ben Moore |
| Mar 29th, 2019 | Using Lasserre Hierarchy for Graph Coloring | Julian Romero |
| Apr 5th, 2019 | Choose from list below, or suggest | To Be Claimed |
-
Claimed ‘NP-Hardness of Coloring 2-Colorable Hypergraphs with Poly-Logarithmically Many Colors’ by Amey Bhangale. http://drops.dagstuhl.de/opus/volltexte/2018/9019/pdf/LIPIcs-ICALP-2018-15.pdf
-
To be claimed ‘Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number’ by David Zuckerman. http://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf
-
To be claimed ‘Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold’ by Delcourt, Perarnau, and Postle. https://arxiv.org/pdf/1804.04025.pdf (This result was presented by Michelle Delcourt at the Tutte Colloquium on 14th September 2018)
-
To be claimed ‘Polynomial bounds for centered colorings on proper minor-closed graph classes’ by Pilipczuk and Siebertz. https://arxiv.org/abs/1807.03683