10 problems

Let $G$ and $H$ be undirected loopless graphs. Their sum $G+H$ is the disjoint union, and their Shannon capacities are … where $G^k$ is the $k$-fold strong product and $\alpha$ den…

Let $\mathsf{G}$ and $\mathsf{H}$ be graphs, and let $\mathsf{G}+\mathsf{H}$ denote their disjoint union. Their Shannon capacities are denoted by $\Theta(\mathsf{G})$ and…

Perturbation conjecture. We moreover conjecture that

Let $G=C_5$ be the cycle graph on five vertices, let $n$ be a positive integer, and let $G^{\boxtimes n}$ denote the $n$-fold strong product of $G$. Sonnemann's conjecture. … This…

Let $C_n$ denote the cycle graph on $n$ vertices, let $C_n^p$ be its $p$-fold strong graph power, let $\alpha(C_n^p)$ be the independence number of $C_n^p$, and let $\Theta(C_n)$ d…

Let $G$ be a graph, and let $\Theta_q(G)$ and $\Theta_*(G)$ denote its quantum and entanglement-assisted Shannon capacities, respectively. Quantum capacity conjecture. For every gr…

Let $G$ be a graph, and let $\Theta_*(G)$ be its entanglement-assisted Shannon capacity. Let $\vartheta(G)$ be the Lovász theta function. Entanglement-assisted capacity conjecture.…

Let $G$ be a graph, and let $\Theta(G)$, $\Theta_q(G)$, and $\Theta_*(G)$ denote its classical, quantum, and entanglement-assisted Shannon capacities, respectively. Quantum–entangl…

Let $G$ be a finite simple graph. Its Shannon capacity is … where $\alpha(G)$ is the independence number and $G^{\boxtimes n}$ is the $n$-th strong graph product power. Lovász's co…

XOR game graph conjecture. The restriction used to prove class-1 behavior can be lifted: a necessary and sufficient condition for a game graph to satisfy