A word-representable graph is a simple graph $G$ which can be represented by a word $w$ over the vertices of $G$ such that any two vertices are adjacent in $G$ if and only if they alternate in $w$. It is known that the class of comparability graphs -- the graphs which admit a transitive orientation -- is precisely the class of graphs that can be represented by a concatenation of permutations of vertices. The class of bipartite graphs is a subclass of comparability graphs. While it is an open problem to determine the representation number of comparability graphs, it was conjectured that the representation number of bipartite graphs on $n$ vertices is at most $n/4$. In this paper, we propose a polynomial time relabeling algorithm to produce a word representing a given bipartite graph which is a concatenation of permutations of the graph's vertices. Thus we obtain an upper bound for the representation number of bipartite graphs, which in turn gives us an upper bound for the dimension of the posets corresponding to bipartite graphs.
翻译：单代表图形是一个简单的图表$G$, 可以用一个单字以美元表示, 以美元为顶点, 也就是说, 任何两个顶点都相邻于$G$, 如果而且只有以美元交替。 已知可比性图表的类别 -- -- 承认过渡方向的图表 -- -- 正好是能够以圆形组合形式表示的图表类别。 两边图表的类别是比较图表的子类。 虽然确定可比性图表的表示数是一个公开的问题, 但据推测, 美元顶点的双面图的表示数最多为$/ 4美元。 在本文中, 我们提议一个多元时间重新标签算法来生成一个单词, 代表某双面图的调数。 因此, 我们获得了双面图的表示数的上框, 反之, 表示一个双面图的顶端。
相关内容
微信扫码咨询专知VIP会员