Shannon Capacity, Lovász Theta Number and the Mycielski Construction
Shannon Capacity, Lovász Theta Number and the Mycielski Construction
We investigate the effect of the well-known Mycielski construction on the Shannon capacity of graphs and on one of its most prominent upper bounds, the (complementary) Lovász theta number. We prove that if the Shannon capacity of a graph, the distinguishability graph of a noisy channel, is attained by some …