Chromatic Symmetric Functions of Conjoined Graphs

Abstract

We introduce path-conjoined graphs defined for two rooted graphs by joining their roots with a path, and investigate the chromatic symmetric functions of its two generalizations: spider-conjoined graphs and chain-conjoined graphs. By using the composition method developed by Zhou and the third author recently, we obtain neat positive e_I-expansions for the chromatic symmetric functions of clique-path-cycle graphs, path-clique-path graphs, and clique-clique-path graphs. We pose the e-positivity conjecture for hat-chains.

Keywords

Chromatic symmetric function / conjoined graph / e-positivity / Stanley–Stembridge’s conjecture / 05E05 / 05A15

References

[1] Aliniaeifard F., Wang V., van Willigenburg S., The chromatic symmetric function of a graph centred at a vertex. Electron. J. Combin., 2024, 31(4): Paper No. 4.22, 34 pp.

[2] Banaian E., Celano K., Chang-Lee M., Colmenarejo L., Goff O., Kimble J., Kimpel L., Lentfer J., Liang J., Sundaram S., The e-positivity of the chromatic symmetric function for twinned paths and cycles. 2024, arXiv:2405.17649

[3] Brosnan P, Chow Timothy Y. Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties. Adv. Math., 2018, 329: 955-1001

[4] Chmutov S., Kazarian M., Lando S., Polynomial graph invariants and the KP hierarchy. Selecta Math. (N.S.), 2020, 26(3): Paper No. 34, 22 pp.

[5] Cho S, Huh J. On e-positivity and e-unimodality of chromatic quasi-symmetric functions. SIAM J. Discrete Math., 2019, 33(4): 2286-2315

[6] Dahlberg S, Foley A, van Willigenburg S. Resolving Stanley’s e-positivity of claw-contractible-free graphs. J. Eur. Math. Soc. (JEMS), 2020, 22(8): 2673-2696

[7] Dahlberg S, van Willigenburg S. Lollipop and lariat symmetric functions. SIAM J. Discrete Math., 2018, 32(2): 1029-1039

[8] Foley A.M., Hoàng C., Merkel O., Classes of graphs with e-positive chromatic symmetric function. Electron. J. Combin., 2019, 26(3): Paper No. 3.51, 19 pp.

[9] Gebhard D, Sagan B. A chromatic symmetric function in noncommuting variables. J. Algebraic Combin., 2001, 13(3): 227-255

[10] Guay-Paquet M., A modular relation for the chromatic symmetric functions of (3+1)-free posets. 2013, arXiv:1306.2400

[11] Hamel A, Hoàng C, Tuero J. Chromatic symmetric functions and H-free graphs. Graphs Combin., 2019, 35(4): 815-825

[12] Hikita T., A proof of the Stanley–Stembridge conjecture. 2024, arXiv:2410.12758

[13] Kato S., A geometric realization of the chromatic symmetric function of a unit interval graph. 2024, arXiv:2410.12231

[14] Li EYH, Li GMX, Wang DGL, Yang ALB. The twinning operation on graphs does not always preserve e-positivity. Taiwanese J. Math., 2021, 25(6): 1089-1111

[15] Li G.M.X., Yang A.L.B., On the e-positivity of (claw, 2K₂)-free graphs. Electron. J. Combin., 2021, 28(2): Paper No. 2.40, 14 pp.

[16] Loebl M. Chromatic polynomial, q-binomial counting and colored Jones function. Adv. Math., 2007, 211(2): 546-565

[17] McDonough J., Pylyavskyy P., Wang S., The Stanley–Stembridge conjecture for 2 + 1 + 1-avoiding unit interval orders: a diagrammatic proof. 2024, arXiv:2404.07280

[18] Noble SD, Welsh DJA. A weighted graph polynomial from chromatic invariants of knots. Ann. Inst. Fourier (Grenoble), 1999, 39(3): 1057-1087

[19] Orellana R, Scott G. Graphs with equal chromatic symmetric functions. Discrete Math., 2014, 320: 1-14

[20] Shareshian J, Wachs ML. Eulerian quasisymmetric functions. Adv. Math., 2010, 225(6): 2921-2966

[21] Shareshian J, Wachs ML. Chromatic quasisymmetric functions. Adv. Math., 2016, 295: 497-551

[22] Stanley RP. A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math., 1995, 111(1): 166-194

[23] Stanley RP. Enumerative Combinatorics, Vol. 1, 2012Second EditionCambridge, Cambridge University Press49

[24] Stanley RP, Stembridge J. On immanants of Jacobi–Trudi matrices and permutations with restricted position. J. Combin. Theory Ser. A, 1993, 62(2): 261-279

[25] Tang D.Q.B., Wang D.G.L., Positive e-expansions of the chromatic symmetric functions of KPKPs, twinned lollipops, and kayak paddles. 2024, arXiv:2408.01385

[26] Thibon J.-Y., Wang D.G.L., A noncommutative approach to the Schur positivity of chromatic symmetric functions. 2023, arXiv:2305.07858

[27] Tom F., A signed e-expansion of the chromatic quasisymmetric function. 2023, arXiv: 2311.08020

[28] Tom F., A signed e-expansion of the chromatic symmetric function and some new e-positive graphs. Sém. Lothar. Combin., 2024, 91B: Art. 48, 12 pp.

[29] Tom F., Vailaya A., Adjacent cycle-chains are e-positive. 2024, arXiv:2410.21762

[30] Topcu H, Sorgun S, Haemers WH. On the spectral characterization of pineapple graphs. Linear Algebra Appl., 2016, 507: 267-273

[31] Tsujie S. The chromatic symmetric functions of trivially perfect graphs and cographs. Graphs Combin., 2018, 34(5): 1037-1048

[32] Wang D.G.L., All cycle-chords are e-positive. 2024, arXiv:2405.01166

[33] Wang DGL, Wang MMY. The e-positivity of two classes of cycle-chord graphs. J. Algebraic Combin., 2023, 57(2): 495-514

[34] Wang D.G.L., Zhou J.Z.F., Composition method for chromatic symmetric functions: Neat noncommutative analogs. 2024, arXiv:2401.01027

[35] Zheng K., On the e-positivity of trees and spiders. J. Combin. Theory Ser. A, 2022, 189: Paper No. 105608, 22 pp.

RIGHTS & PERMISSIONS

Peking University