Chromatic symmetric functions and H-free graphs

DOI10.1007/S00373-019-02034-1zbMATH Open1416.05105arXiv1709.03354OpenAlexW2963800967WikidataQ128119426 ScholiaQ128119426MaRDI QIDQ2000573FDOQ2000573

Chính T. Hoàng, Jake E. Tuero, Angèle. M. Hamel

Publication date: 28 June 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Two celebrated conjectures in chromatic symmetric function theory concern the positivity chromatics symmetric functions of claw-free graphs. Here we extend the claw-free idea to general graphs and consider the e-positivity question for H-free graphs where H = {claw, F} and H={claw, F, co-F}, where F is a four-vertex graph. We settle the question for all cases except H={claw, co-diamond}, and we provide some partial results in that case.

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

zbMATH Keywords

claw-free graphschromatic symmetric function\(e\)-positive

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• A symmetric function generalization of the chromatic polynomial of a graph
• Vertex coloring of graphs with few obstructions
• 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
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Paw-free graphs
• The chromatic symmetric functions of trivially perfect graphs and cographs
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Proof of a conjecture on immanants of the Jacobi-Trudi matrix
• Immanants of combinatorial matrices
• Chromatic bases for symmetric functions

Cited In (13)

• Graphs with equal chromatic symmetric functions
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• Schur and \(e\)-positivity of trees and cut vertices
• Marked Graphs and the Chromatic Symmetric Function
• Chromatic symmetric functions in noncommuting variables revisited
• On Stanley's chromatic symmetric function and clawfree graphs
• Classes of graphs with \(e\)-positive chromatic symmetric function
• On the \(e\)-positivity of \((claw, 2K_2)\)-free graphs
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• A combinatorial formula for the Schur coefficients of chromatic symmetric functions
• Recoloring some hereditary graph classes
• On the chromatic number of certain highly symmetric graphs
• The twinning operation on graphs does not always preserve \(e\)-positivity

This page was built for publication: Chromatic symmetric functions and \(H\)-free graphs

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