dc.contributor.author | Hallam, Joshua | |
dc.contributor.author | Martin, Jeremy L. | |
dc.contributor.author | Sagan, Bruce E. | |
dc.date.accessioned | 2021-02-15T22:27:03Z | |
dc.date.available | 2021-02-15T22:27:03Z | |
dc.date.issued | 2018-11-01 | |
dc.identifier.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. | en_US |
dc.identifier.uri | http://hdl.handle.net/1808/31428 | |
dc.description.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. | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | © 2018 Elsevier Ltd. All rights reserved. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | en_US |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | en_US |
dc.subject | Chromatic polynomial | en_US |
dc.subject | Graph | en_US |
dc.subject | Increasing forest | en_US |
dc.subject | Perfect elimination order | en_US |
dc.subject | Simplicial complex | en_US |
dc.title | Increasing spanning forests in graphs and simplicial complexes | en_US |
dc.type | Article | en_US |
kusw.kuauthor | Martin, Jeremy L. | |
kusw.kudepartment | Mathematics | en_US |
dc.identifier.doi | 10.1016/j.ejc.2018.09.011 | en_US |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | en_US |
kusw.oapolicy | This item meets KU Open Access policy criteria. | en_US |
dc.rights.accessrights | openAccess | en_US |