The chromatic polynomial of a digraph

DOI10.1007/978-3-030-63072-0_1MaRDI QIDQ2056880zbMATH OpenOpenAlexFDO

Authors Winfried. Hochstättler, Johanna Wiehe

Publication date 8 December 2021

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

zbMATH Keywords

face latticechromatic polynomialflow polynomialdichromatic numbertotally cyclic subdigraphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Stochastic network models in operations research (90B15)

Abstract: An acyclic coloring of a digraph as defined by Neumann-Lara is a vertex-coloring such that no monochromatic directed cycles occur. Counting the number of such colorings with $k$ colors can be done by counting so-called Neumann-Lara-coflows (NL-coflows), which build a polynomial in $k$. We will present a representation of this polynomial using totally cyclic subdigraphs, which form a graded poset $Q$. Furthermore we will decompose our NL-coflow polynomial, which becomes the chromatic polynomial of a digraph by multiplication with the number of colors to the number of components, examining the special structure of the poset of totally cyclic subdigraphs with fixed underlying undirected graph. This decomposition will confirm the equality of our chromatic polynomial of a digraph and the chromatic polynomial of the underlying undirected graph in the case of symmetric digraphs.

Recommendations

• The dichromatic polynomial of a digraph
• The chromatic polynomial of a graph
• On the chromatic polynomial of a graph
• The chromatic polynomial for cycle graphs
• scientific article; zbMATH DE number 4095494
• scientific article; zbMATH DE number 833904
• scientific article; zbMATH DE number 568845
• Chromatic polynomials of connected graphs
• Chromatic polynomials of hypergraphs
• Chromatic polynomials of hypergraphs

Cites work

• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3687449 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A flow theory for the dichromatic number
• Combinatorial Reciprocity Theorems
• Cycle reversions and dichromatic number in tournaments
• Dichromatic number and fractional chromatic number
• Graph theory
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Planar digraphs of digirth four are 2-colorable
• Some extremal results in cochromatic and dichromatic theory
• The 3 and 4-dichromatic tournaments of minimum order
• The NL-flow polynomial
• The circular chromatic number of a digraph
• The dichromatic number of a digraph

Cited in

(7)

• The Digraph Drop Polynomial
• A Dichromatic Polynomial for Weighted Graphs and Link Polynomials
• Dichromatic polynomial of product digraphs
• Tutte polynomials for regular oriented matroids
• scientific article; zbMATH DE number 3319302 (Why is no real title available?)
• The NL-flow polynomial
• The dichromatic polynomial of a digraph

This page was built for publication: The chromatic polynomial of a digraph

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