On graph products and multi-word-representability

Abstract

The multi-word-representation number $\hat{I}¼(G)$ is the minimum number of word-representable graphs whose union is $G$. We investigate $\hat{I}¼(H)$ for graph products $H$ obtained from $G_1$ and $G_2$ via six fundamental products: lexicographic, Cartesian, rooted, corona, tensor, and strong. We prove $\hat{I}¼(H)=\max \{\hat{I}¼(G_1),\hat{I}¼(G_2)\}$ for Cartesian and rooted products. For the corona product, we show $\max \{\hat{I}¼(G_1),\hat{I}¼(G_2)\}\le \hat{I}¼(H)\le \max \{\hat{I}¼(G_1),\hat{I}¼(G_2)\}+1$, and show that the lower bound is tight when $\hat{I}¼(G_1)>\hat{I}¼(G_2)$ or $G_2$ admits a covering by $\hat{I}¼(G_2)$ word-representable graphs, one of which is a comparability graph. For the lexicographic product, we show $\max \{\hat{I}¼(G_1),\hat{I}¼(G_2)\}\le \hat{I}¼(H)\le \hat{I}¼(G_1)+\hat{I}¼(G_2)$, and show that the lower bound is tight when ${\mathrm{cov}}_{\mathrm{comp}}(G_2)\le \max \{\hat{I}¼(G_1),\hat{I}¼(G_2)\}$. We provide logarithmic bounds for tensor and strong products. We prove $G^{[k]}$ is word-representable if and only if $G$ is a comparability graph. We establish bounds $\hat{I}¼(G^{[k]})\le {\mathrm{cov}}_{\mathrm{comp}}(G)$ and $\hat{I}¼(G^{[k]})\le k$ for non-comparability word-representable graphs. Using lexicographic powers, we obtain the sublinear bound $\ddot{I}„(n)\le n^{{\log }_{8}6+\hat{I}\mu }$ for the extremal function $\ddot{I}„(n)$. Finally, we address the Word-representable Bipartition (WB) problem, proving a negative answer for $n\ge 2593$: showing that for every such $n$, there exists a graph of order $n$ that cannot be vertex-partitioned into two word-representable induced subgraphs.