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^15) 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
  1. 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

  2. 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

  3. To be claimed ‘Rapid mixing of Glauber dynamics for colorings below Vigoda’s 116 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)

  4. To be claimed ‘Polynomial bounds for centered colorings on proper minor-closed graph classes’ by Pilipczuk and Siebertz. https://arxiv.org/abs/1807.03683