Open Problem Garden

It is a consequence of a theorem of Tutte that a cubic graph has a nowhere-zero 4-flow if and only if it is 3-edge-colorable. Thus, the 4-flow conjecture implies that every bridgeless cubic graph with no Petersen minor is 3-edge-colorable (another conjecture of Tutte). Note that the Four Color Theorem is equivalent to the assertion that planar cubic graphs without bridges are 3-edge-colorable, so even this weaker conjecture is a strengthening of the Four Color Theorem. This weaker conjecture was recently proved by Robertson, Seymour, and Thomas [RST]. Their proof involves a reduction to the case of nearly planar graphs, and then an application of 4-color-theorem type techniques (computer assisted) to color these graphs.

Most conjectures about flows can be easily reduced to the case of cubic graphs by splitting arguments. The idea is to take a vertex incident with edges and "split" , that is, replace by two new vertices and , and for every edge join it to either or (sometimes the edge is also added). For instance, this technique can be used to reduce the general 5-flow conjecture down to the special case of cubic graphs. Unfortunately, that technique does not apply here, since splitting a vertex may introduce a Petersen minor.

Petersen's graph is not an apex graph (deleting any vertex still leaves a nonplanar graph). It follows that no apex graph can have a Petersen minor, so the above conjecture implies that every bridgeless apex graph has a nowhere-zero 4-flow. By splitting the vertices which lie in the plane this can be reduced to the special case where all vertices which lie in the plane have degree 3. This is then equivalent to the following old conjecture of Gr\"{o}tzsch.

Conjecture  (Gr\"{o}tzsch)   If is a 2-connected connected planar graph of maximum degree 3, then is 3-edge-colorable unless it has exactly one vertex of degree 2.