Counting Methods for Nowhere-Zero Flows: Applications of Linear Algebra by Counting Nowhere-Zero Flows and Edge Colorings in Graphs

by Martin Kochol

Flows in graphs present an important topic in modern mathematics with many applications in practice and a significant impact on many problems from discrete mathematics. Nowhere-zero flow in graphs present a dual concept for graph coloring problems. We apply methods of linear algebra for nowhere-zero flow problems. We present several results regarding the 5-flow conjecture. In particular, we give restrictions regarding cyclical edge connectivity and girth for a smallest counterexample to the conjecture. We present also application for edge-coloring of planar cubic graphs. Furthermore we present a decomposition formula for flow polynomials on graphs. The book is devoted for graduate students and researchers dealing with combinatorics.

120 pages, Paperback

Published March 28, 2011