Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871901 | Discrete Applied Mathematics | 2016 | 9 Pages |
Abstract
A generalized vertex join of a graph is obtained by joining an arbitrary multiset of its vertices to a new vertex. We present a low-order polynomial time algorithm for computing the chromatic polynomials of generalized vertex joins of trees; by duality, this algorithm can also be used to compute the flow polynomials of arbitrary outerplanar graphs. We also present closed formulas for the chromatic polynomials of generalized vertex joins of cliques, and the chromatic and flow polynomials of generalized vertex joins of cycles.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Boris Brimkov, Illya V. Hicks,