Cell coloring and Tutte's 3-flow conjecture
November 30, 2023, 12:20 in S6
We introduce cell colorings of drawings of graphs in the plane. By the 4-color theorem, every drawing of a bridgeless graph has a cell 4-coloring. A drawing of a graph is cell 2-colorable if and only if the underlying graph is Eulerian. We will also see that every graph without degree 1 vertices admits a cell 3- colorable drawing. The hardest question however is: When can every drawing of a graph be cell 3-colored? We show that every 4-edge-connected graph and every graph admitting a nowhere-zero 3-flow is universally cell 3-colorable. We also discuss circumstances under which universal cell 3-colorability guarantees the existence of a nowhere-zero 3-flow because of its connection to the 3-flow-conjecture. We make a generalized 3-flow conjecture and prove our conjecture for subcubic and for K3,3-minor-free graphs.