グラフの隣り合っている頂点を異なる色で塗り分ける割り当てをグラフの彩色という.
n 色での彩色の総数は n に関する多項式になっており,これは彩色多項式と呼ばれるよく知られた不変量である.
各彩色に対し,色を不定元と考え,それらの積を取ることにより単項式を得ることができる.
彩色すべてに渡るこれら単項式の総和は彩色対称関数と呼ばれ,彩色多項式よりも真に強い不変量である.
Stanley は,彩色対称関数は木の完全不変量であると予想している.
また,Gasharov は claw-free グラフの彩色対称関数は s-positive になると予想している.
本講演では,グラフに対するいくつかの操作で生成されるクラスについて考察し,
Stanley の予想の類似と Gasharov の予想の部分結果について紹介する.
戻る