A reminder: this is today.
-----------------------------------------------------
On 2023-11-27 22:06, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 30 November, given by Felix Schröder. Please find the talk details below.
Best regards, Misha Tyomkyn.
Cell coloring and Tutte's 3-flow conjecture Felix Schröder Charles University November 30, 2023, 12:20 in S6
Abstract 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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz