Back to Search
Start Over
A flow theory for the dichromatic number.
- Source :
-
European Journal of Combinatorics . Dec2017, Vol. 66, p160-167. 8p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *FLOWGRAPHS
*PLANAR graphs
*GRAPHIC methods
*GRAPH theory
*COMBINATORICS
Subjects
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 66
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 124936525
- Full Text :
- https://doi.org/10.1016/j.ejc.2017.06.020