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.

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

1 Answer 1

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.