On weak chromatic polynomials of mixed graphs

DOI10.1007/S00373-013-1381-1zbMATH Open1306.05100arXiv1210.4634OpenAlexW2013943456MaRDI QIDQ489344FDOQ489344

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 20 January 2015

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

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.

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

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

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)

Cites Work

• Acyclic orientations of graphs
• Ordered structures and partitions
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• Mixed graph edge coloring
• Mixed graph colorings
• Scheduling Problems and Mixed Graph Colorings
• On Counting Generalized Colorings
• Title not available (Why is that?)

Cited In (7)

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

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)