Approximate capacity of index coding for some classes of graphs
Fatemeh Arbabjolfaei, Young-Han Kim · 2016
For a class of index coding problems with side information graph having the Ramsey number R(i, j) upper bounded by ciajb, it is shown that the clique covering scheme approximates the broadcast rate within a multiplicative factor of O(na+b/a+b+1), where n is the number of messages. Based on this result and known bounds on Ramsey numbers, it is demonstrated that the broadcast rate of planar graphs, line graphs, and fuzzy circular interval graphs can be approximated within a factor of (2n)2/3.