A flow theory for the dichromatic number. (December 2017)

• Record Type: Journal Article
• Authors: Hochstättler, Winfried
• Is Part Of: European journal of combinatorics. Volume 66(2017)
• Page Start: 160
• Page End: 167
• Publication Date: 2017-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.06.020
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We transfer Tutte's theory for analyzing the chromatic number of a graph using nowhere-zero-coflows and -flows (NZ-flows) to the dichromatic number of a digraph and define Neumann-Lara-flows (NL-flows). We prove that any digraph whose underlying (multi-)graph is 3 -edge-connected admits a NL-3-flow, and even a NL-2-flow in case the underlying graph is 4 -edge connected. We conjecture that 3 -edge-connectivity already guarantees the existence of a NL-2-flow, which, if true, would imply the 2-Color-Conjecture for planar graphs due to Víctor Neumann-Lara. Finally we present an extension of the theory to oriented matroids.