Nowhere-zero flow polynomials. (English) Zbl 1055.05062
Summary: We introduce certain flow polynomials associated with digraphs and use them to study nowhere-zero flows from a commutative algebraic perspective. Using Hilbert’s Nullstellensatz, we establish a relation between nowhere-zero flows and dual flows. For planar graphs this gives a relation between nowhere-zero flows and flows of their planar duals. It also yields an appealing proof that every bridgeless triangulated graph has a nowhere-zero four-flow.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C75 | Structural characterization of families of graphs |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
Keywords:
Flow; Nowhere zero flow; Coloring; Tait coloring; Planar graph; Four color theorem; Five flow conjecture; Gröbner basis; Nullstellensatz; Algebraic combinatorics; Graph polynomial; Tutte polynomial; Chordal graphReferences:
| [1] | Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049 |
| [2] | Babson, E.; Onn, S.; Thomas, R. R., The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases, Adv. Appl. Math., 30, 529-544 (2003) · Zbl 1039.13018 |
| [3] | F. Jaeger, On nowhere-zero flows in multigraphs, in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proceedings of the Fifth British Combinatorial Conference; Congr. Numer. XV (1976) 373-378.; F. Jaeger, On nowhere-zero flows in multigraphs, in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proceedings of the Fifth British Combinatorial Conference; Congr. Numer. XV (1976) 373-378. · Zbl 0324.90023 |
| [4] | Lovász, L., Stable sets and polynomials, Discrete Math., 124, 137-153 (1994) · Zbl 0792.05082 |
| [5] | P.D. Seymour, Nowhere-zero flows, in: R. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, pp. 289-299.; P.D. Seymour, Nowhere-zero flows, in: R. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, pp. 289-299. · Zbl 0845.05035 |
| [6] | Tait, P. G., On the colouring of maps, Proc. Roy. Soc. Edinburgh, 10, 501-503 (1878-1880) · JFM 12.0408.02 |
| [7] | Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101 |
| [8] | D.J.A. Welsh, Matroids: fundamental concepts, in: R. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, pp. 481-526.; D.J.A. Welsh, Matroids: fundamental concepts, in: R. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, pp. 481-526. · Zbl 0853.05023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
