Edge-coloring 8-regular planar graphs
Edge-coloring 8-regular planar graphs
-
Maria Chudnovsky, Columbia University
Fine Hall 224
In 1974 Seymour made the following conjecture: Let G be a k-regular planar (multi)graph, such that for every odd set X of vertices of G, at least k edges of G have one end in X and the other in V(G) \ X. Then G is k-edge colorable. For k=3 this is equivalent to the four-color theorem. The cases k=4,5 were solved by Guenin, the case k=6 by Dvorak, Kawarabayashi and Kral, and the case k=7 by Edwards and Kawarabayashi. In joint work with Edwards and Seymour, we now have a proof for the case k=8, and that is the topic of this talk.