标题： 关于二分图表示数猜想 显示英文标题

标题： On the Conjecture of the Representation Number of Bipartite Graphs

摘要： 确定任意字可表图的表示数问题是 NP-难问题，即使对于二分图来说该问题仍然是开放的。 表示数对于某些二分图是已知的，包括所有顶点数最多为9的图。 对于具有大小分别为$m$和$n$的两部分集的二分图，Glen 等人. 推测表示数至多为$\lceil \frac{m+n}{4}\rceil$，其中$m+n \ge 9$。 在本文中，我们证明了每个二分图都是$\left( 1+ \lceil \frac{m}{2} \rceil \right)$-可表的，其中$m$是其最小的部分集的大小。 此外，如果$m$为奇数，则我们证明二分图是$\lceil \frac{m}{2} \rceil $- 可表征的。 因此，我们确立了 Glen 等人的猜想对于所有二分图成立，除了部分集大小相等且为偶数的二分图。 对于部分集大小相等且为偶数的二分图，我们使用邻域包含图方法证明了该猜想的一些子类情况。 显示英文摘要

摘要： While the problem of determining the representation number of an arbitrary word-representable graph is NP-hard, this problem is open even for bipartite graphs. The representation numbers are known for certain bipartite graphs including all the graphs with at most nine vertices. For bipartite graphs with partite sets of sizes $m$ and $n$, Glen et al. conjectured that the representation number is at most $\lceil \frac{m+n}{4}\rceil$, where $m+n \ge 9$. In this paper, we show that every bipartite graph is $\left( 1+ \lceil \frac{m}{2} \rceil \right)$-representable, where $m$ is the size of its smallest partite set. Furthermore, if $m$ is odd then we prove that the bipartite graphs are $\lceil \frac{m}{2} \rceil $-representable. Accordingly, we establish that the conjecture by Glen et al. holds good for all bipartite graphs leaving the bipartite graphs whose partite sets are of equal and even size. In case of the bipartite graphs with partite sets of equal and even size, we prove the conjecture for certain subclasses using the neighborhood inclusion graph approach.