Classes of graphs with e-positive chromatic symmetric function

zbMATH Open1420.05177arXiv1808.03391MaRDI QIDQ2325752FDOQ2325752

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)

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.

Full work available at URL: https://arxiv.org/abs/1808.03391

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

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)