ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Increasing spanning forests in graphs and simplicial complexes
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 |