Increasing spanning forests in graphs and simplicial complexes

View/ Open
Issue Date
2018-11-01Author
Hallam, Joshua
Martin, Jeremy L.
Sagan, Bruce E.
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Rights
© 2018 Elsevier Ltd. All rights reserved. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Metadata
Show full item recordAbstract
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.
Collections
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.
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.