Nowhere-zero flow polynomials

DOI10.1016/j.jcta.2004.06.011zbMath1055.05062arXivmath/0309347OpenAlexW1976596704MaRDI QIDQ703684

Shmuel Onn

Publication date: 11 January 2005

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0309347

zbMATH Keywords

Gröbner basisAlgebraic combinatoricsFlowTutte polynomialNullstellensatzColoringTait coloringChordal graphFive flow conjectureFour color theoremGraph polynomialNowhere zero flowPlanar graph

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ On the complexity of Hilbert refutations for partition ⋮ Parity, Eulerian subgraphs and the Tutte polynomial ⋮ Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares

Cites Work

• Colorings and orientations of graphs
• Stable sets and polynomials
• The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases.
• A Contribution to the Theory of Chromatic Polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nowhere-zero flow polynomials