On Stanley's chromatic symmetric function and clawfree graphs (Q1301848): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q1389787 |
||
Property / author | |||
Property / author: Vesselin N. Gasharov / rank | |||
Revision as of 18:21, 27 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On Stanley's chromatic symmetric function and clawfree graphs |
scientific article |
Statements
On Stanley's chromatic symmetric function and clawfree graphs (English)
0 references
9 April 2000
0 references
A proper coloring of a simple graph \(G\) (without loops and multiple edges) with vertex set \(V=\{v_1,\ldots,v_d\}\) is a function \(\kappa: V\to {\mathbb{N}}^+\) such that \(\kappa(u)\not=\kappa(v)\) if \(u\) and \(v\) are vertices of an edge of \(G\). Stanley associated to \(G\) the symmetric function \(X_G=X_G(x_1,x_2,\ldots)=\sum x_{\kappa(v_1)}\ldots x_{\kappa(v_d)}\), where the sum ranges over all proper colorings \(\kappa\) of \(G\). He also conjectured that if \(G\) is a claw-free graph (i.e. does not contain \(K_{1,3}\) as an induced subgraph) then the function \(X_G\) is Schur positive, i.e. is a nonnegative linear combination of Schur functions. A statement which is equivalent to the Stanley conjecture is that every minor of the Toeplitz matrix \(A=[e_{j-i}^G]_{i,j\geq 0}\) is a polynomial with nonnegative coefficients, where \(e_n^G=e_n^G(v_1,\ldots,v_d)= \sum_S(\prod_{v\in S}v)\), \(S\) runs over all \(n\)-element stable subsets of \(V\), and ``stable'' means that no two vertices are joined by an edge. One of the main results of the paper under review is a combinatorial proof that the \(2\times 2\) minors of the matrix \(A\) have nonnegative coefficients. This provides supportive evidences for the Stanley conjecture, generalizes a result of Krattenthaler and gives a new proof of a result of Hamidoune that the stable set polynomial \(\sum_{n\geq 0}e_n^G(1,1,\ldots,1)t^n\) related with a claw-free graph is log-concave. Finally, the author characterizes the claw-free graphs in terms of cardinalities of stable sets.
0 references
claw-free graphs
0 references
symmetric functions
0 references
Schur positive functions
0 references
proper colorings of graphs
0 references