The chromatic polynomial of a digraph

DOI10.1007/978-3-030-63072-0_1zbMATH Open1479.05163arXiv1911.09547OpenAlexW2990136770MaRDI QIDQ2056880FDOQ2056880

Authors: Winfried. Hochstättler, Johanna Wiehe 

Publication date: 8 December 2021

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)