arXiv:1012.3847 Abstract | arXiv Analytics

arXiv:1012.3847 [math.CO]Abstract References Reviews Resources

Chromatic polynomials of complementary (n,k)-clique pairs

Published 2010-12-17, updated 2011-06-07Version 3

We introduce a class of pairs of graphs consisting of two cliques joined by an arbitrary number of edges. The members of a pair have the property that the clique-bridging edge-set of one graph is the complement of that of the other. We prove a precise relation between the chromatic polynomials of the graphs in such a pair, showing that they have the same splitting field, and that the number of acyclic orientations of each graph is determined by the number of proper vertex-colourings of the other.

Comments: Replaced by a longer version, containing this note as a subsection

Categories: math.CO

Keywords: chromatic polynomials, complementary, arbitrary number, precise relation, acyclic orientations

Related articles: Most relevant | Search more

arXiv:1412.3685 [math.CO] (Published 2014-12-11)

Acyclic orientations and poly-Bernoulli numbers

P. J. Cameron, C. A. Glass, R. U. Schumacher

arXiv:math/9907078 [math.CO] (Published 1999-07-12)

Sinks in Acyclic Orientations of Graphs

David D. Gebhard, Bruce E. Sagan

arXiv:0907.0046 [math.CO] (Published 2009-07-01)

A geometric approach to acyclic orientations