Skip to main content
2 of 2
added 151 characters in body
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

Random graphs might show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

It seems unlikely that the maximal cliques are conspiring to share vertices. More worrying is that the maximal cliques might not all have the same size, but perhaps enough of them do, or can be fixed up without doing too much damage to the independence number.

Ben Barber
  • 4.6k
  • 2
  • 25
  • 38