View PDF HTML (experimental)

Abstract:The multi-word-representation number $\mu(G)$ is the minimum number of word-representable graphs whose union is $G$. We investigate $\mu(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 $\mu(H) = \max\{\mu(G_1), \mu(G_2)\}$ for Cartesian and rooted products. For the corona product, we show $\max\{\mu(G_1), \mu(G_2)\} \le \mu(H) \le \max\{\mu(G_1), \mu(G_2)\} + 1$, and show that the lower bound is tight when $\mu(G_1) > \mu(G_2)$ or $G_2$ admits a covering by $\mu(G_2)$ word-representable graphs, one of which is a comparability graph. For the lexicographic product, we show $\max\{\mu(G_1), \mu(G_2)\} \le \mu(H) \le \mu(G_1) + \mu(G_2)$, and show that the lower bound is tight when $\mathrm{cov}_{\mathrm{comp}}(G_2) \le \max\{\mu(G_1), \mu(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 $\mu(G^{[k]}) \le \mathrm{cov}_{\mathrm{comp}}(G)$ and $\mu(G^{[k]}) \le k$ for non-comparability word-representable graphs. Using lexicographic powers, we obtain the sublinear bound $\tau(n) \le n^{\log_8 6+\epsilon}$ for the extremal function $\tau(n)$. Finally, we address the Word-representable Bipartition (WB) problem, proving a negative answer for $n \geq 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.

Submission history

From: Sreyas Sasidharan [view email]
[v1] Tue, 31 Mar 2026 11:52:38 UTC (359 KB)
[v2] Fri, 3 Apr 2026 19:59:05 UTC (263 KB)
[v3] Wed, 3 Jun 2026 17:47:11 UTC (25 KB)
[v4] Mon, 8 Jun 2026 17:16:14 UTC (27 KB)
[v5] Mon, 29 Jun 2026 17:56:05 UTC (32 KB)