The NL-flow polynomial

DOI10.1016/J.DAM.2020.02.011MaRDI QIDQ2664009zbMATH OpenOpenAlexFDO

Authors Barbara Altenbokum, Winfried. Hochstättler, Johanna Wiehe

Publication date 20 April 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

equivalence theoremflow polynomialtournamentsdichromatic numberoriented regular matroids

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21)

Abstract: In 1982 V'{i}ctor Neumann-Lara introduced the dichromatic number of a digraph $D$ as the smallest integer $k$ such that the vertices $V$ of $D$ can be colored with $k$ colors and each color class induces an acyclic digraph. Later a flow theory for the dichromatic number transferring Tutte's theory of nowhere-zero flows (NZ-flows) from classic graph colorings has been developed by Hochst"attler. The purpose of this paper is to pursue this analogy by introducing a new definition of algebraic Neumann-Lara-flows (NL-flows) and a closed formula for their polynomial. Furthermore we generalize the Equivalence Theorem for nowhere-zero flows to NL-flows in the setting of regular oriented matroids. Finally we discuss computational aspects of computing the NL-flow polynomial for orientations of complete digraphs and obtain a closed formula in the acyclic case.

Recommendations

• A flow theory for the dichromatic number
• The chromatic polynomial of a digraph
• The dichromatic polynomial of a digraph
• Nowhere-zero flow polynomials
• List coloring digraphs

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A flow theory for the dichromatic number
• Digraphs. Theory, algorithms and applications
• Graph theory
• On the enumeration of chains in regular chain-groups
• The Tutte polynomial
• The dichromatic number of a digraph
• Triangulations. Structures for algorithms and applications

Cited in

(3)

• A flow theory for the dichromatic number
• Tutte polynomials for regular oriented matroids
• The chromatic polynomial of a digraph

This page was built for publication: The NL-flow polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664009)