Combinatorics Seminar

When: Sunday, November 17, 10am
Where: Schreiber 309
Speaker: Jarek Grytczuk, Warsaw University of Technology
Title: : Graph polynomials and choosability of planar graphs

Abstract:

A graph $G$ is $k$-choosable if it is colorable from arbitrary lists of colors, each of size $k$, assigned to the vertices of $G$. A famous theorem of Thomassen asserts that every planar graph is 5-choosable, whereas Voigt found planar graphs that are not 4-choosable.

Recently, Zhu reproved Thomassen's theorem by using graph polynomials and the celebrated Combinatorial Nullstellensatz. By using similar approach we proved that every planar graph can be made 4-choosable by deleting a suitable matching. This strengthens some earlier results on defective choosability of planar graphs, and perhaps kindles some hope for a computer-free proof of the Four Color Theorem. We will discuss some possible directions towards this extravagant goal.

Joint work with Xuding Zhu.