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

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

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.

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

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• 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.
• 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 Roberts characterization of proper and unit interval graphs
• The chromatic symmetric functions of trivially perfect graphs and cographs
• The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture

Cited in

(25)

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

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)