On weak chromatic polynomials of mixed graphs

DOI10.1007/S00373-013-1381-1MaRDI QIDQ489344zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 20 January 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4634, https://authors.library.caltech.edu/53799/

zbMATH Keywords

mixed graphposetcombinatorial reciprocity theorem\(\omega\)-labelingorder polynomialweak chromatic polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07)

Abstract: A emph{mixed graph} is a graph with directed edges, called arcs, and undirected edges. A $k$-coloring of the vertices is proper if colors from $1,2,\mathrm{...},k$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge, and the color of $u$ is less than or equal to (resp. strictly less than) the color of $v$ if $uv$ is an arc. The weak (resp. strong) chromatic polynomial of a mixed graph counts the number of proper $k$-colorings. Using order polynomials of partially ordered sets, we establish a reciprocity theorem for weak chromatic polynomials giving interpretations of evaluations at negative integers.

Recommendations

• On two coloring problems in mixed graphs
• Mixed graph colorings
• The edge chromatic number of a directed/mixed multigraph
• Lower bounds for the colored mixed chromatic number of some classes of graphs.
• Pseudo-chordal mixed hypergraphs

Cites work

• scientific article; zbMATH DE number 3549019 (Why is no real title available?)
• Acyclic orientations of graphs
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• Mixed graph colorings
• Mixed graph edge coloring
• On Counting Generalized Colorings
• Ordered structures and partitions
• Scheduling Problems and Mixed Graph Colorings

Cited in

(8)

• Chromatic quasisymmetric class functions for combinatorial Hopf monoids
• Partial graph orientations and the Tutte polynomial
• Coloring complexes and combinatorial Hopf monoids
• Bivariate chromatic polynomials of mixed graphs
• First kind weak total chromatic numbers of graphs \(C_m\vee F_n\), \(C_m\vee W_n\) and \(C_m\vee C_n\)
• Bijective proofs of proper coloring theorems
• On the differential polynomial of a graph
• On Cohen-Macaulay Hopf monoids in species

This page was built for publication: On weak chromatic polynomials of mixed graphs

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