Graph theory versus minimum rank for index coding
Karthikeyan Shanmugam, Alexandros G. Dimakis, Michael L. Langberg · 2014
We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far1. 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.