Gopalan Sajith

Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan

Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class in graph theory. Comparability graphs form a subclass of word-representable graphs. Both classes are hereditary and hence admit characterizations in terms of forbidden induced subgraphs. While the minimal forbidden induced subgraphs for comparability graphs are known, a complete characterization for word-representable graphs remains open. In this paper, we investigate which minimal non-comparability graphs are also minimal non-word-representable graphs. To this end, we classify minimal non-comparability graphs according to whether they are word-representable or not, and thereby determine exactly which of them belong to the class of minimal non-word-representable graphs. As a consequence, we obtain a complete description of minimal non-word-representable graphs containing an all-adjacent vertex. We also consider an open problem posed by Kenkireth et al.\ concerning the cover number of word-representable graphs by comparability graphs. We show that there exist triangle-free word-representable graphs whose cover number by comparability graphs is at least $Ω(\log\log n)$. For triangle-free circle graphs, we prove that the cover number by comparability graphs is at most $3$, and that this bound is tight. More generally, we show that every circle graph $G$ with clique number $ω(G) \ge 24$ has cover number at most $2$. Finally, we identify four subclasses of word-representable graphs in which every graph has cover number at most $2$.

Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan

We investigate the relationship between the lexicographic product of graphs and their multi-word-representation number. Although the lexicographic product of two word-representable graphs need not itself be word-representable, a precise characterization has not previously been established. We provide a complete characterization, showing that for word-representable graphs $G_1$ and $G_2$, the lexicographic product $G_1 \circ G_2$ is word-representable if and only if $G_2$ is a comparability graph. For lexicographic powers, we prove that $G^{[k]}$ is word-representable if and only if $G$ is a comparability graph. The multi-word-representation number $μ$ for lexicographic powers and products satisfies the following bounds. If $G$ is a non-comparability graph, then $μ(G^{[k]}) \le k$, whereas if $G$ is the union of two comparability graphs, then $μ(G^{[k]}) = 2$. More generally, for graphs $G_1$ and $G_2$ with $μ(G_1) = k_1$ and $μ(G_2) = k_2$, the lexicographic product $H = G_1 \circ G_2$ satisfies the upper bound $μ(H) \le k_1 + k_2$. This bound is tight, with equality $μ(H) = k_1$, when $k_1 \ge k_2$ and $G_2$ is the union of $k_1$ comparability graphs. Moreover, if $G_1$ and $G_2$ are minimal non-word-representable graphs, then $μ(G_1 \circ G_2) \le 3$. Finally, we study the function $τ(n)$, which measures the size of the largest word-representable induced subgraph guaranteed in every $n$-vertex graph. By constructing extremal graphs via lexicographic powers, we establish a sublinear upper bound, showing that $τ(n) \le n^{0.86}$ for sufficiently large $n$.