Flows and matchings in graphs

Graph coloring theory is a cornerstone of discrete mathematics, occupying a central position. Research on the 4-Color Conjecture (established as the 4-Color Theorem since 1976) has significantly influenced graph theory. Tait (1880) demonstrated that the 4-Color Theorem is equivalent to the statement that every planar bridgeless cubic graph is 3-edge-colorable. Moreover, it is equivalent to the statement that every planar bridgeless cubic graph has an even 2-factor and that every bridgeless planar graph has a nowhere-zero 4-flow. In this study, we will investigate these relationships in a broader context, examining edge colorings of graphs subject to constraints imposed by color classes, and nowhere-zero flows on (signed) graphs.

Sponsor: Sino-German (CSC-DAAD) Postdoc Scholarship Program