2
$\begingroup$

Consider the Steiner triple system $S(2,3,n)$ for a suitable integer $n$. We define a graph $G$ with all the vertices as precisely the blocks of the above steiner triple system and any two points adjacent iff the intersection of the blocks corresponding to them in the STS are non-empty.

Are there results on the choosability of such graphs? Or, at least, is anything known about the chromatic number of such graphs? I think these numbers are closely related to the chromatic number and choosability of the generalized Kneser graph $K(n,3,2)$. The maximum degree of these graphs seems to be $\frac{3(n-2)}{2}$ and the clique size is $\frac{n-2}{2}$. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
1
  • $\begingroup$ @bof thanks and sorry! edited $\endgroup$
    – vidyarthi
    Commented Aug 20, 2020 at 8:56

1 Answer 1

Reset to default
1
$\begingroup$

The said graph can be seen as the line graph of a rank three linear hypergraph. Some results on list coloring of this is known here. The list chromatic number of this is bounded above by $n$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .