Graph theory versus minimum rank for index coding

We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far
¹
. Further, we establish a rather strong negative result: all known graph theoretic bounds are within a logarithmic factor from the chromatic number. This is in striking contrast to minrank since prior work has shown that it can outperform the chromatic number by a polynomial factor in some cases. The conclusion is that all known graph theoretic bounds are not much stronger than the chromatic number.