Description
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 p
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
roved 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