Списочная раскраска графа, соответствующего системе троек Штейнера

Aug 20 2020

Рассмотрим систему троек Штейнера $S(2,3,n)$ для подходящего целого числа $n$. Определим граф$G$ со всеми вершинами точно так же, как блоки указанной выше системы троек Штейнера и любые две смежные точки тогда и только тогда, когда пересечение соответствующих им блоков в STS непусто.

Есть ли результаты о возможности выбора таких графов? Или, по крайней мере, известно что-нибудь о хроматическом числе таких графов? Я думаю, что эти числа тесно связаны с хроматическим числом и возможностью выбора обобщенного графа Кнезера.$K(n,3,2)$. Максимальная степень этих графиков кажется$\frac{3(n-2)}{2}$ а размер клики $\frac{n-2}{2}$. Есть подсказки? Заранее спасибо.

Ответы

1 vidyarthi Aug 22 2020 at 23:16

Указанный граф можно рассматривать как линейный граф линейного гиперграфа третьего ранга. Некоторые результаты по раскраске этого списка известны здесь . Список хроматического числа этого ограничен сверху$n$.