Friday, November 5, 2010 — 3:30 PM to 4:30 PM EDT

From 3-colorings to 3-flows

Speaker: Dan Younger
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Every loopless planar graph that is triangle-free has a vertex 3-colouring. This is Grötzsch's Theorem, put forward in 1958. Late in time, perhaps: we think of it now, anachronistically, as the case k = 3 of Tutte's 1954 k- Flow Conjectures: The famous general statements about planar k-vertex- colourings, k = 3, 4, 5, generalise to k-flows of a general graph, with the Petersen graph exception for k = 4. The statement for k = 3: Every graph without 1- or 3-cut has a 3-flow. None of these conjectures is settled. In 2003, Carsten Thomassen gave a proof of Grötzsch's Theorem, in its vertex-colouring statement, or rather, as a list-colouring statement, a proof that makes no appeal to the Euler Polyhedron Formula. To do this struck me as intrinsically good, and as a first step towards Tutte's vision. It was to study Carsten's paper that Bruce Richter and I started meeting together. Soon enough, we moved on to our own version. We were joined in this venture, for a time, by Cândida Nunes da Silva of the University of Campinas, who went on to include a version in her recent doctoral thesis. When we reached the stage where no evolutionary improvement to the vertex-colouring version presented itself, the door to a 3-flow proof opened. 

I will present a proof of Grötzsch's Theorem in the dual, in terms of 3-flows, a proof that needs no appeal to Euler's Polyhedron Formula. The proof still requires properties of the plane. But we think it a second step toward Tutte's vision, in a case he did not at first envisage, k = 3. 

This is joint work with Bruce Richter.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (139)
    1. October (10)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)