Semi-transitive orientations and word-representable graphs. Discrete
Semi-transitive orientations and word-representable graphs. Discrete
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Halldorsson;S. Kitaev
中科院分区：
文献类型：
--
作者：
M. Halldorsson;S. Kitaev
.一个图G =（V，E）是一个词可表示图，如果在字母表V上存在一个词W，使得字母x和y在W中交替当且仅当（x，y）∈ E，对于每个x ∈ = y。在本文中，我们给出了一个有效的字表示图的方向的特征。也就是说，我们证明了一个图是词表示的当且仅当它允许一个半传递方向的文件中定义的。这使我们能够证明一些关于词表示图的结果，特别是表明识别问题是在NP中，并且词表示图包括所有3-着色图。我们还探讨了代表图的词的大小的界限。G的表示数是最小的k，使得G可以用一个词表示，其中每个字母出现k次;这样的k存在于任何词可表示的图中。我们证明了n个顶点上的词可表示图的表示数至多为2 n，而存在n/ 2的图. ,
. 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. ,