Classes of graphs with e-positive chromatic symmetric function

MaRDI QIDQ2325752zbMATH OpenFDO

Authors Angèle M. Foley, Chính T. Hoàng, Owen Merkel

Publication date 30 September 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.03391, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p51

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Symmetric functions and generalizations (05E05)

Abstract: In the mid-1990s, Stanley and Stembridge conjectured that the chromatic symmetric functions of claw-free co-comparability (also called incomparability) graphs were e-positive. The quest for the proof of this conjecture has led to an examination of other, related graph classes. In 2013 Guay-Paquet proved that if unit interval graphs are e-positive, that implies claw-free incomparability graphs are as well. Inspired by this approach, we consider a related case and prove that unit interval graphs whose complement is also a unit interval graph are e-positive. We introduce the concept of strongly $e$-positive to denote a graph whose induced subgraphs are all e-positive, and conjecture that a graph is strongly e-positive if and only if it is (claw, net)-free.

Review text

Summary: \textit{R. P. Stanley} and \textit{J. R. Stembridge} [J. Comb. Theory, Ser. A 62, No. 2, 261--279 (1993; Zbl 0772.05097)] conjectured that the chromatic symmetric functions of claw-free co-comparability (also called incomparability) graphs were \(e\)-positive. The quest for the proof of this conjecture has led to an examination of other, related graph classes. \textit{M. Guay-Paquet} [``A modular relation for the chromatic symmetric functions of (3+1) free posets, Preprint, \url{arXiv:1306.2400}] proved that if unit interval graphs are \(e\)-positive, that implies claw-free incomparability graphs are as well. Inspired by this approach, we consider a related case and prove that unit interval graphs whose complement is also a unit interval graph are \(e\)-positive. We introduce the concept of strongly \(e\)-positive to denote a graph whose induced subgraphs are all \(e\)-positive, and conjecture that a graph is strongly \(e\)-positive if and only if it is (claw, net)-free.

Recommendations

• Graphs with equal chromatic symmetric functions
• Chromatic symmetric functions and \(H\)-free graphs
• The chromatic symmetric functions of trivially perfect graphs and cographs
• A symmetric function generalization of the chromatic polynomial of a graph
• Chromatic symmetric function of graphs from Borcherds algebras
• The chromatic quasisymmetric class function of a digraph
• On the chromatic equivalence class of graphs
• On a class of finite symmetric graphs
• On the chromatic number of certain highly symmetric graphs
• Marked Graphs and the Chromatic Symmetric Function

Cites work

• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Chromatic classical symmetric functions
• Chromatic quasisymmetric functions
• Chromatic symmetric functions and \(H\)-free graphs
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• On \(e\)-positivity and \(e\)-unimodality of chromatic quasisymmetric functions
• On claw-free asteroidal triple-free graphs
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• On the Co-P₃ -Structure of Perfect Graphs
• Representation of a finite graph by a set of intervals on the real line
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• The chromatic symmetric functions of trivially perfect graphs and cographs
• The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture
• The Roberts characterization of proper and unit interval graphs

Cited in

(33)

• Chromatic symmetric functions and \(H\)-free graphs
• On the \(e\)-positivity of \((claw, 2K_2)\)-free graphs
• Modular relations of the Tutte symmetric function
• The twinning operation on graphs does not always preserve e-positivity
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• A combinatorial expansion of vertical-strip LLT polynomials in the basis of elementary symmetric functions
• Plethysms of chromatic and Tutte symmetric functions
• A combinatorial formula for the Schur coefficients of chromatic symmetric functions
• A deletion-contraction relation for the chromatic symmetric function
• Chromatic symmetric functions in noncommuting variables revisited
• Melting lollipop chromatic quasisymmetric functions and Schur expansion of unicellular LLT polynomials
• Schur and \(e\)-positivity of trees and cut vertices
• A new formula for Stanley's chromatic symmetric function for unit interval graphs and E-positivity for triangular ladder graphs
• On \(e\)-positivity and \(e\)-unimodality of chromatic quasisymmetric functions
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• The \(e\)-positivity of two classes of cycle-chord graphs
• Graphs with equal chromatic symmetric functions
• On $e$-Positivity and $e$-Unimodality of Chromatic Quasi-symmetric Functions
• A complete multipartite basis for the chromatic symmetric function
• Marked Graphs and the Chromatic Symmetric Function
• Homogeneous sets in graphs and a chromatic multisymmetric function
• The chromatic symmetric function of a graph centred at a vertex
• The e-positivity of some new classes of graphs
• Chromatic symmetric functions of conjoined graphs
• A signed e-expansion of the chromatic quasisymmetric function
• When is the chromatic quasisymmetric function symmetric?
• Clocks are e-positive
• The e-positivity of the chromatic symmetric function for twinned paths and cycles
• A signed e-expansion of the chromatic symmetric function and some new e-positive graphs
• When is the chromatic quasisymmetric function symmetric?
• On the Stanley-Stembridge conjecture
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs

This page was built for publication: Classes of graphs with \(e\)-positive chromatic symmetric function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325752)