On graph products and multi-word-representability

arXiv:2603.29629v3 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 four standard graph products: the lexicographic, Cartesian, rooted, and corona products. For the Cartesian and rooted products, we show that the multi-word-representation number of the product equals $\max\{\mu(G_1),\mu(G_2)\}$. For the corona product, we prove that it is at most $\max\{\mu(G_1),\mu(G_2)\}+1$, and we identify a condition under which equality with the maximum holds. For the lexicographic product, we establish the bound $\mu(G_1 \circ G_2) \le \mu(G_1) + \mu(G_2)$, which reduces to $\max\{\mu(G_1),\mu(G_2)\}$ when the cover number of $G_2$ by comparability graphs is at most $\max\{\mu(G_1),\mu(G_2)\}$. We also characterize the case when the lexicographic product of two minimal non-word-representable graphs has $\mu=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]}) \le$ the cover number of $G$ by comparability graphs. 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$.