Loading...
Increasing spanning forests in graphs and simplicial complexes
Hallam, Joshua ; Martin, Jeremy L. ; Sagan, Bruce E.
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
Collections
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.