Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 52 min ago
PreprintCC BY 4.0arXiv

Proper circular arc graphs are e-positive

  • Aarush Vailaya
Open at sourcePDFDOICite

Abstract

We prove an e-positive formula for the chromatic symmetric function of proper circular arc graphs solving the q=1 case of a conjecture of Ellzey and of Alexandersson and Panova. In doing so, we provide a new proof of the e-positivity of unit interval graphs, which alongside Guay-Paquet's reduction gives a new proof of the Stanley--Stembridge conjecture. We define color matrices, which count proper colorings, and tableau matrices, whose entries are nonnegative rational numbers and ratios of elementary symmetric functions. We prove the two matrices are related by a single family of change of basis matrices, which become invertible after restricting to finitely many colors, and we show the chromatic symmetric function of proper circular arc graphs comes from taking the trace of these matrices. Using Hikita's tableaux, this gives an explicit formula for the chromatic symmetric function of a proper circular arc graph as a weighted sum over tableaux whose first and last k vertices lie in the same columns.

Related

  1. Proper conflict-free choosability of sparse graphs with girth at least seven
    Xingqin Qi, Huimin Song, Zhulou Cao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Positive Weighted Curvatures on Compact Manifolds with Weighted Convex Boundary and Proper Manifolds
    Ruifeng Xu
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  3. Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
    Huijuan Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Bounded-Defect Proper Orientations and Graphs on Surfaces
    Qi Wu, Yong Lu
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  5. Strictly proper scoring rules for node selection tasks on graphs
    Lorenz Hilfiker, Nathan Cincera Brack, Martin Sterchi
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{vailaya2026proper,
  title = {{Proper circular arc graphs are $e$-positive}},
  author = {Aarush Vailaya},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.33124},
  eprint = {2609.33124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33124},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Proper circular arc graphs are e-positive
AU  - Aarush Vailaya
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2609.33124
UR  - https://arxiv.org/abs/2609.33124
AB  - We prove an e-positive formula for the chromatic symmetric function of proper circular arc graphs solving the q=1 case of a conjecture of Ellzey and of Alexandersson and Panova. In doing so, we provide a new proof of the e-positivity of unit interval graphs, which alongside Guay-Paquet's reduction gives a new proof of the Stanley--Stembridge conjecture. We define color matrices, which count proper colorings, and tableau matrices, whose entries are nonnegative rational numbers and ratios of elementary symmetric functions. We prove the two matrices are related by a single family of change of basis matrices, which become invertible after restricting to finitely many colors, and we show the chromatic symmetric function of proper circular arc graphs comes from taking the trace of these matrices. Using Hikita's tableaux, this gives an explicit formula for the chromatic symmetric function of a proper circular arc graph as a weighted sum over tableaux whose first and last k vertices lie in the same columns.
ER  -