Leírás
The Shannon OR-capacity C_OR(G) of a graph G is defined as C_OR(G)=lim_{t -> to infty}sqrt[t]{omega(G^t)} where G^t is an appropriately defined graph exponentiation (and omega stands for clique number). Lovász proved C_OR(C_5)=sqrt{5} with the help of his famous theta number. The Mycielski construction is one of the standard constructions showing that a triangle-free graph can have arbitrarily large chromatic number. From a graph G it produces graph M(G) having the same clique number while the chromatic number increases by 1. We investigate the effect of this construction on the complementary Lovász theta number and on Shannon OR-capacity. For the former we prove that the theta number of the Mycielski of a graph is determined by the theta number of the original graph and give an explicit formula for it. For Shannon OR-capacity we show that C_OR(M(G))>C_OR(G) whenever there exists a k such that C_OR(G)=sqrt[k]{omega(G^k)}.
Az eredmények Simonyi Gáborral közösek.
Zoom ID 296 194 6869
or
https://zoom.us/j/2961946869?omn=98603280031