The NL-flow polynomial

DOI10.1016/J.DAM.2020.02.011zbMATH Open1461.05082arXiv1901.01871OpenAlexW3008428165MaRDI QIDQ2664009FDOQ2664009

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

Publication date: 20 April 2021

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Graph theory
• A Contribution to the Theory of Chromatic Polynomials
• Triangulations. Structures for algorithms and applications
• The Tutte polynomial
• On the enumeration of chains in regular chain-groups
• Title not available (Why is that?)
• Digraphs. Theory, algorithms and applications
• The dichromatic number of a digraph
• A flow theory for the dichromatic number

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)