[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