Semi-transitive orientations and word-representable graphs

详细信息    查看全文

• 作者：Magnú ; s M. Halldó ; rsson^a ; ^{mmh@ru.is" class="auth_mail" title="E-mail the corresponding author} ; Sergey Kitaev^b ; ^{sergey.kitaev@cis.strath.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Artem Pyatkin^c ; ^{artem@math.nsc.ru" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graphs ; Words ; Orientations ; Word-representability ; Complexity ; Circle graphs ; Comparability graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 March 2016
• 年：2016
• 卷：201
• 期：Complete
• 页码：164-171
• 全文大小：401 K

文摘

A graph G=(V,E)$G=(V,E)$ is a word-representable graph   if there exists a word W$W$ over the alphabet V$V$ such that letters x$x$ and y$y$ alternate in W$W$ if and only if (x,y)∈E$(x,y)\in E$ for each x≠y$x\ne 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$G$ is the minimum k$k$ such that G$G$ is a representable by a word, where each letter occurs k$k$ times; such a k$k$ exists for any word-representable graph. We show that the representation number of a word-representable graph on n$n$ vertices is at most 2n$2n$, while there exist graphs for which it is n/2$n/2$.