Semi-transitive orientations and word-representable graphs

Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

10 Citations (Scopus)

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.
LanguageEnglish
Pages164-171
Number of pages14
JournalDiscrete Applied Mathematics
Volume201
Early online date24 Aug 2015
DOIs
Publication statusPublished - 11 Mar 2016

Fingerprint

Graph in graph theory
If and only if
Alternate

Keywords

  • graphs
  • comparability graphs
  • circle graphs
  • complexity
  • word-representability
  • orientations

Cite this

Halldórsson, Magnús M. ; Kitaev, Sergey ; Pyatkin, Artem. / Semi-transitive orientations and word-representable graphs. In: Discrete Applied Mathematics. 2016 ; Vol. 201. pp. 164-171.
@article{6bd041b541884009b2e4cc88ef353ff1,
title = "Semi-transitive orientations and word-representable graphs",
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.",
keywords = "graphs, comparability graphs, circle graphs, complexity, word-representability, orientations",
author = "Halld{\'o}rsson, {Magn{\'u}s M.} and Sergey Kitaev and Artem Pyatkin",
year = "2016",
month = "3",
day = "11",
doi = "10.1016/j.dam.2015.07.033",
language = "English",
volume = "201",
pages = "164--171",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

Semi-transitive orientations and word-representable graphs. / Halldórsson, Magnús M.; Kitaev, Sergey; Pyatkin, Artem.

In: Discrete Applied Mathematics, Vol. 201, 11.03.2016, p. 164-171.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Semi-transitive orientations and word-representable graphs

AU - Halldórsson, Magnús M.

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2016/3/11

Y1 - 2016/3/11

N2 - 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.

AB - 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.

KW - graphs

KW - comparability graphs

KW - circle graphs

KW - complexity

KW - word-representability

KW - orientations

UR - http://www.sciencedirect.com/science/article/pii/S0166218X15003868

U2 - 10.1016/j.dam.2015.07.033

DO - 10.1016/j.dam.2015.07.033

M3 - Article

VL - 201

SP - 164

EP - 171

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -