Semi-transitive orientations and word-representable graphs

Halldórsson, Magnús M. and Kitaev, Sergey and Pyatkin, Artem (2016) Semi-transitive orientations and word-representable graphs. Discrete Applied Mathematics, 201. pp. 164-171. ISSN 0166-218X (https://doi.org/10.1016/j.dam.2015.07.033)

[thumbnail of Halldorsson-etal-DAM-2015-Semi-transitive-orientations-and-word-representable]
Preview
 Text. Filename: Halldorsson_etal_DAM_2015_Semi_transitive_orientations_and_word_representable.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (180kB)| Preview

Abstract

A graph G=(V,E) is a \emph{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 \emph{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 2n, while there exist graphs for which it is n/2.

CORE (COnnecting REpositories)