On graph products and multi-word-representability

arXiv:2603.29629v4 Announce Type: replace-cross Abstract: The multi-word-representation number $\mu(G)$ of a graph $G$ is the minimum number of word-representable graphs whose union is $G$. We study the behavior of $\mu$ under six standard graph products: the lexicographic, Cartesian, rooted, corona, tensor, and strong products. For the Cartesian and rooted products, we show that $\mu(G_1 \square G_2)=\mu(G_1 \diamond G_2)=\max\{\mu(G_1),\mu(G_2)\}$. For the corona product, we prove that $\mu(G_1 \odot G_2)\le \max\{\mu(G_1),\mu(G_2)\}+1$, and we identify a condition under which equality holds. For the lexicographic product, we establish $\mu(G_1 \circ G_2)\le \mu(G_1)+\mu(G_2)$, which reduces to $\max\{\mu(G_1),\mu(G_2)\}$ under a comparability cover condition on $G_2$, and we characterize the case when the lexicographic product of two minimal non-word-representable graphs has $\mu=2$. For the tensor product $G_1 \times G_2$, we show $\mu(G_1 \times G_2)\le \log_3(\min\{\chi(G_1),\chi(G_2)\})$. For the strong product $G_1 \boxtimes G_2$, we establish $\max\{\mu(G_1),\mu(G_2)\}\le \mu(G_1 \boxtimes G_2)\le \max\{\mu(G_1),\mu(G_2)\}+\log_3(\min\{\chi(G_1),\chi(G_2)\})$. For lexicographic powers $G^{[k]}$, we prove that $\mu(G^{[k]})\le k$ when $G$ is word-representable but not a comparability graph, and in general $\mu(G^{[k]})$ is bounded by the comparability cover number of $G$. We further show that $G^{[k]}$ is word-representable if and only if $G$ is a comparability graph. As an application, we obtain a sublinear upper bound on the extremal function $\tau(n)$, defined as the largest integer such that every $n$-vertex graph contains a word-representable induced subgraph of that size; in particular, $\tau(8^k)\le 6^k$, implying $\tau(n)\le n^{\log_8 6+\epsilon}$ for large $n$.