Loading...
Thumbnail Image
Publication

Increasing spanning forests in graphs and simplicial complexes

Hallam, Joshua
Martin, Jeremy L.
Sagan, Bruce E.
Citations
Altmetric:
Abstract
Let G be a graph with vertex set {1,...,n}. A spanning forest F of G is increasing if the sequence of labels on any path starting at the minimum vertex of a tree of F forms an increasing sequence. Hallam and Sagan showed that the generating function ISF(G, t) for increasing spanning forests of G has all nonpositive integral roots. Furthermore they proved that, up to a change of sign, this polynomial equals the chromatic polynomial of G precisely when 1,..., n is a perfect elimination order for G. We give new, purely combinatorial proofs of these results which permit us to generalize them in several ways. For example, we are able to bound the coef- cients of ISF(G, t) using broken circuits. We are also able to extend these results to simplicial complexes using the new notion of a cage-free complex. A generalization to labeled multigraphs is also given. We observe that the de nition of an increasing spanning forest can be formulated in terms of pattern avoidance, and we end by exploring spanning forests that avoid the patterns 231, 312 and 321.
Description
Date
2018-11-01
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Research Projects
Organizational Units
Journal Issue
Keywords
Chromatic polynomial, Graph, Increasing forest, Perfect elimination order, Simplicial complex
Citation
Joshua Hallam, Jeremy L. Martin, Bruce E. Sagan, "Increasing spanning forests in graphs and simplicial complexes", European Journal of Combinatorics, Volume 76, 2019, Pages 178-198, ISSN 0195-6698, https://doi.org/10.1016/j.ejc.2018.09.011.
Embedded videos