A Caltech Library Service

On Weak Chromatic Polynomials of Mixed Graphs

Beck, Matthias and Blado, Daniel and Crawford, Joseph and Jean-Louis, Taïna and Young, Michael (2015) On Weak Chromatic Polynomials of Mixed Graphs. Graphs and Combinatorics, 31 (1). pp. 91-98. ISSN 0911-0119.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A 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, . . . , k} are assigned to each vertex such that u and v have different colors if uν is an edge, and the color of u is less than or equal to (resp. strictly less than) the color of ν if uν 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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© 2013 Springer Japan. Received: 21 October 2012; Revised: 20 October 2013; Published online: 12 December 2013. We thank Thomas Zaslavsky and two anonymous referees for various helpful suggestions about this paper, and Ricardo Cortez and the staff at MSRI for creating an ideal research environment at MSRI-UP. This research was partially supported by the US National Science Foundation through the Grants DMS-1162638 (Beck), DMS-0946431 (Young), and DMS-1156499 (MSRI-UP REU), and by the US National Security Agency through grant H98230-11-1-0213.
Funding AgencyGrant Number
National Security Agency (NSA)H98230-11-1-0213
Subject Keywords:Weak chromatic polynomial; Mixed graph; Poset; ω-Labeling; Order polynomial; Combinatorial reciprocity theorem
Issue or Number:1
Classification Code:MSC 2000: Primary 05C15; Secondary 05A15, 06A07
Record Number:CaltechAUTHORS:20150115-153436487
Persistent URL:
Official Citation:Beck, M., Blado, D., Crawford, J. et al. Graphs and Combinatorics (2015) 31: 91. doi:10.1007/s00373-013-1381-1
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53799
Deposited By: Tony Diaz
Deposited On:15 Jan 2015 23:43
Last Modified:03 Oct 2019 07:52

Repository Staff Only: item control page