[talks] K Edwards general exam
Melissa M. Lawson
mml at CS.Princeton.EDU
Mon May 6 15:02:06 EDT 2013
Katherine Edwards will present her research seminar/general exam on Friday
May 10 at 2PM in room 302. The members of her committee are: Paul
Seymour (Math) advisor, Moses Charikar, and Mark Braverman. Everyone is
invited to attend her talk and those faculty wishing to remain for the oral exam
following are welcome to do so. Her abstract and reading list follow below.
-----------------------------
Edge-coloring 7- and 8-regular planar graphs
In 1974, Seymour conjectured the following: 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) nX. 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 Chudnovsky and Seymour, we now have a proof for the case k = 8,
and that is the topic of this talk.
Reading list
[1] Paolo Codato, Michele Conforti, and Claudia Sera ni. Packing t-joins. Journal of Graph
Theory, 22(4):293{296, 1996.
[2] WJ Cook, WH Cunningham, WR Pulleyblank, and A Schrijver. Combinatorial Opti-
mization. 1998. New York, NY: Wiley-Interscience.
[3] Bertrand Guenin. Packing t-joins and edge colouring in planar graphs. 2003.
[4] Penny Haxell and Jessica McDonald. On characterizing vizing's edge colouring bound.
Journal of Graph Theory, 69(2):160-168, 2012.
[5] Takao Nishizeki and Kenichi Kashiwagi. On the 1.1 edge-coloring of multigraphs. SIAM
Journal on Discrete Mathematics, 3(3):391-410, 1990.
[6] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour
theorem. Journal of Combinatorial Theory, Series B, 70(1):2 -44, 1997.
[7] P.D. Seymour. The matroids with the max-flow min-cut property. Journal of Combina-
torial Theory, Series B, 23(2-3):189-222, 1977.
[8] P.D. Seymour. On multi-colourings of cubic graphs, and conjectures of fulkerson and
tutte. Proc. London Math. Soc, 38(3):423-460, 1979.
[9] P.D. Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London
Mathematical Society, 3(1):178-192, 1981.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130506/95a048b2/attachment.html>
More information about the talks
mailing list