Semi-transitive orientations and word-representable graphs
Semi-transitive orientations and word-representable graphs
复制标题
DOI：
10.1016/j.dam.2015.07.033
复制
发表时间：
2015-01
期刊：
影响因子：
--
通讯作者：
M. Halldórsson;S. Kitaev;A. Pyatkin
中科院分区：
文献类型：
--
作者：
M. Halldórsson;S. Kitaev;A. Pyatkin
图G=（V， E）是一个词可表示的图，当且仅当(x, y)∈E且每个x≠y时，在字母V上存在一个词W，使得字母x和y在W中交替存在。本文给出了词可表示图的方向的有效刻画。也就是说，我们证明了一个图当且仅当它具有文中定义的半传递取向时是词可表示的。这使我们能够证明一些关于词可表示图的结果，特别是表明识别问题是NP的，并且词可表示图包括所有的3色图。我们还探讨了表示图的单词的大小的界限。G的表示数是最小k，使得G可以用一个词来表示，其中每个字母出现k次；这样的k对于任何可词表示的图都存在。我们证明了n个顶点上的可词表示图的表示数最多为2n，而存在表示数为n/2的图。
Abstract A graph G=(V, E) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y)∈ E for each x≠ y. In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n, while there exist graphs for which it is n/2.