シュタイナートリプルシステムに対応するグラフのリストカラーリング
Aug 20 2020
シュタイナートリプルシステムを検討してください $S(2,3,n)$ 適切な整数の場合 $n$。グラフを定義します$G$ すべての頂点が上記のシュタイナートリプルシステムのブロックとまったく同じであり、STSでそれらに対応するブロックの交点が空でない場合は隣接する任意の2つのポイントがあります。
そのようなグラフの選択可能性に関する結果はありますか?または、少なくとも、そのようなグラフの彩色数について何か知られていますか?これらの数値は、一般化されたクネーザーグラフの彩色数と選択可能性に密接に関連していると思います。$K(n,3,2)$。これらのグラフの最大次数は$\frac{3(n-2)}{2}$ クリークサイズは $\frac{n-2}{2}$。ヒントはありますか?よろしくお願いします。
回答
1 vidyarthi Aug 22 2020 at 23:16
上記のグラフは、ランク3の線形ハイパーグラフの折れ線グラフとして見ることができます。これのリストカラーリングに関するいくつかの結果はここで知られています。このリストの色数は、上記で制限されています。$n$。