Semitransitive orientations and wordrepresentable graphs
Halldórsson, Magnús M. and Kitaev, Sergey and Pyatkin, Artem (2016) Semitransitive orientations and wordrepresentable graphs. Discrete Applied Mathematics, 201. pp. 164171. ISSN 0166218X

Text (HalldorssonetalDAM2015Semitransitiveorientationsandwordrepresentable)
Halldorsson_etal_DAM_2015_Semi_transitive_orientations_and_word_representable.pdf  Accepted Author Manuscript License: Download (180kB)  Preview 
Abstract
A graph G=(V,E) is a \emph{wordrepresentable 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 wordrepresentable graphs in terms of orientations. Namely, we show that a graph is wordrepresentable if and only if it admits a \emph{semitransitive orientation} defined in the paper. This allows us to prove a number of results about wordrepresentable graphs, in particular showing that the recognition problem is in NP, and that wordrepresentable graphs include all 3colorable 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 wordrepresentable graph. We show that the representation number of a wordrepresentable graph on n vertices is at most 2n, while there exist graphs for which it is n/2.
Item type:  Article 

ID code:  54148 
Keywords:  graphs, comparability graphs, circle graphs, complexity, wordrepresentability, orientations, Mathematics, Discrete Mathematics and Combinatorics, Applied Mathematics 
Subjects:  Science > Mathematics 
Department:  Faculty of Science > Computer and Information Sciences 
Depositing user:  Pure Administrator 
Date deposited:  03 Sep 2015 13:52 
Last modified:  31 Mar 2017 22:23 
Related URLs:  
URI:  http://strathprints.strath.ac.uk/id/eprint/54148 
Export data: 