On chordal graphs and their chromatic polynomials

Authors

  • Geir Agnarsson

DOI:

https://doi.org/10.7146/math.scand.a-14421

Abstract

We derive a formula for the chromatic polynomial of a chordal or a triangulated graph in terms of its maximal cliques. As a corollary we obtain a way to write down an explicit formula for the chromatic polynomial for an arbitrary power of a graph which belongs to any given class of chordal graphs that are closed under taking powers.

Downloads

Published

2003-12-01

Issue

Section

Articles