e-Positive caterpillars have maximum degree at most three
Abstract
Dahlberg, She, and van Willigenburg conjectured that every e-positive tree has maximum degree at most three. We prove this conjecture for caterpillars. Our proof introduces a specialization--cone method: we evaluate chromatic symmetric functions under finite-support specializations that are nonnegative on the elementary symmetric functions, express the evaluations through transfer matrices, and certify negativity using finitely generated cones. Two specializations and three cones handle all caterpillars remaining after a connected-partition reduction, with no bound on the number or spacing of their trivalent vertices. The required cone inclusions and strict sign inequalities are certified by exact rational arithmetic. We also exhibit two infinite families of non-spider caterpillars of maximum degree four that admit connected partitions of every type, showing that Wolfgang's criterion alone leaves cases requiring further obstructions. Our result also reduces Li's criterion on e-positivity for caterpillars of maximum degree three to an explicit condition on the positions of trivalent vertices.
Related
- On the maximum degree and order of Kt-minor-free graphs with positive Lin--Lu--Yau curvature
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- Large induced subgraphs with k vertices of maximum degree
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
BibTeX
@misc{tang2026epositive,
title = {{$e$-Positive caterpillars have maximum degree at most three}},
author = {Davion Q. B. Tang and David G. L. Wang and Monica M. Y. Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39481},
eprint = {2610.39481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39481},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - e-Positive caterpillars have maximum degree at most three
AU - Davion Q. B. Tang
AU - David G. L. Wang
AU - Monica M. Y. Wang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39481
UR - https://arxiv.org/abs/2610.39481
AB - Dahlberg, She, and van Willigenburg conjectured that every e-positive tree has maximum degree at most three. We prove this conjecture for caterpillars. Our proof introduces a specialization--cone method: we evaluate chromatic symmetric functions under finite-support specializations that are nonnegative on the elementary symmetric functions, express the evaluations through transfer matrices, and certify negativity using finitely generated cones. Two specializations and three cones handle all caterpillars remaining after a connected-partition reduction, with no bound on the number or spacing of their trivalent vertices. The required cone inclusions and strict sign inequalities are certified by exact rational arithmetic. We also exhibit two infinite families of non-spider caterpillars of maximum degree four that admit connected partitions of every type, showing that Wolfgang's criterion alone leaves cases requiring further obstructions. Our result also reduces Li's criterion on e-positivity for caterpillars of maximum degree three to an explicit condition on the positions of trivalent vertices.
ER -