Steiner 트리플 시스템에 해당하는 그래프의 목록 색상
Aug 20 2020
Steiner 트리플 시스템을 고려하십시오. $S(2,3,n)$ 적절한 정수 $n$. 우리는 그래프를 정의합니다$G$ 모든 정점을 위의 스테이 너 트리플 시스템의 블록과 STS에서 해당 블록의 교차점이 비어 있지 않은 경우 인접한 두 점으로 정확하게 표시됩니다.
그러한 그래프의 선택 가능성에 대한 결과가 있습니까? 아니면 적어도 그러한 그래프의 색수에 대해 알려진 것이 있습니까? 이 숫자는 일반화 된 Kneser 그래프의 색수 및 선택 가능성과 밀접한 관련이 있다고 생각합니다.$K(n,3,2)$. 이 그래프의 최대 정도는$\frac{3(n-2)}{2}$ 그리고 파벌 크기는 $\frac{n-2}{2}$. 힌트가 있습니까? 미리 감사드립니다.
답변
1 vidyarthi Aug 22 2020 at 23:16
상기 그래프는 랭크 3 선형 하이퍼 그래프의 선 그래프로 볼 수있다. 이것의 목록 색상에 대한 일부 결과는 여기 에 알려져 있습니다 . 이것의 목록 색채 번호는 위에 의해 제한됩니다$n$.