Indexed on: 08 Sep '18Published on: 04 Sep '18Published in: SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2229-2241, January 2018. We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovász theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding.