Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777096 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
Abstract
We prove that, in several settings, a graph has exponentially many nowhere-zero flows. Our results may be seen as a counting alternative to the well-known proofs of existence of Z3-, Z4-, and Z6-flows. In the dual setting, proving exponential number of 3-colorings of planar triangle-free graphs is a related open question due to Thomassen.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák, Bojan Mohar, Robert Å ámal,