Nowhere-zero flow polynomials

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:108

Article

Onn, S

关键词: flow;    nowhere zero flow;    coloring;    Tait coloring;    planar graph;    four color theorem;    five flow conjecture;    Grobner basis;    Nullstellensatz;    algebraic combinatorics;    graph polynomial;    Tutte polynomial;    chordal graph;   

DOI  :  10.1016/j.jcta.2004.06.011

来源: Elsevier

【 摘 要 】

In this article, 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. (C) 2004 Elsevier Inc. All rights reserved.

【 授权许可】

Free