Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs

详细信息    查看全文

• 作者：Boris Brimkov ; ^{boris.brimkov@rice.edu" class="auth_mail" title="E-mail the corresponding author} ; Illya V. Hicks ^{ivhicks@rice.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Chromatic polynomial ; Flow polynomial ; Vertex join ; Outerplanar graph ; Tree ; Wheel graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：13-21
• 全文大小：435 K

文摘

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.