Open Collections

Chromatic Symmetric Functions and H-free Graphs

Banff International Research Station for Mathematical Innovation and Discovery

A key area of investigation in chromatic symmetric functions concerns the e-positivity, and/or Schur positivity, of a particular class of chromatic symmetric functions whose underlying graphs are clawfree. The interest in these graphs originates in a paper of Stanley and Stembridge (On immanants of Jacobi-Trudi matrices and permutations with restricted position, JCTA 62 (1993), 261-279) that considers positivity of coefficients of immanants. A natural consideration in their study is a conjecture that states that if a poset is (3+1)-free, then its incomparability graph, which is necessarily clawfree, is e-positive. As a related result, Gasharov (Incomparability graphs of (3+1)-free posets are s-positive, Disc. Math. 157 (1996), 193-197) proved that they are Schur positive. Stanley (Graph colorings and related symmetric functions: ideas and applications, Disc. Math. 193 (1998), 267-286.) has further conjectured that *any* clawfree graph is Schur positive. In parallel to this, in graph theory, much effort has been spent in characterizing the chromatic characteristics of graphs that are H-free, where H is some set of induced subgraphs. A key question in this domain is, can the chromatic number of a H-free graph be determined in polynomial time? This answer is known for large classes of graphs, but, interestingly, the classification for all combinations of subgraphs with 4 vertices is almost, but not quite, complete, Lozin and Malyshev (Vertex coloring of graphs with few obstructions, Disc. Appl. Math. 216 (2017), 273-280). The claw is a graph on 4 vertices. Do the other graphs on 4 vertices have similar positivity results? In graph theory when it is too hard to say something about a single subgraph, the question of multiple subgraphs is often considered (e.g. if we cannot derive results about clawfree graphs, perhaps we can derive results about (claw, 4-cycle)-free graphs), hence the positivity question can similarly be made easier by asking about a set of subgraphs rather than a single one. Just as the question about clawfree graphs was interesting because of the connection to immanant conjectures, so too would questions about other 4 vertex graphs be interesting because of the parallel with studies in graph theory.

Mathematics; Combinatorics; Group theory and generalizations

video/mp4

Author affiliation: Wilfrid Laurier University

2017-11-11

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63582

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/