Semi-transitive orientations and word-representable graphs

DOI10.1016/J.DAM.2015.07.033MaRDI QIDQ908303zbMATH OpenOpenAlexFDO

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

Publication date 4 February 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.07108

zbMATH Keywords

complexitywordsorientationscomparability graphscircle graphsword representability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

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)inE$ for each $xeqy$. 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$.

Recommendations

• Solving computational problems in the theory of word-representable graphs
• Word-representability of split graphs
• On word-representability of polyomino triangulations
• Word-representability of triangulations of grid-covered cylinder graphs
• Alternation graphs

Cites work

• scientific article; zbMATH DE number 811561 (Why is no real title available?)
• Alternation graphs
• Circle graphs and monadic second-order logic
• Enumerating split-pair arrangements
• Graphs Capturing Alternations in Words
• On representable graphs
• On scheduling cycle shops: Classification, complexity and approximation
• On the complexity of diagram testing
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• The Complexity of the Partial Order Dimension Problem
• The Hardness of Approximating Poset Dimension
• Word problem of the Perkins semigroup via directed acyclic graphs.

Cited in

(29)

• Human-verifiable proofs in the theory of word-representable graphs
• Weakly transitive orientations, Hasse diagrams and string graphs
• Word-representability of Toeplitz graphs
• On the representation number of a crown graph
• An embedding technique in the study of word-representability of graphs
• Word-representability of split graphs generated by morphisms
• Representing split graphs by words
• Word-representability of triangulations of grid-covered cylinder graphs
• New results on word-representable graphs
• Word-representability of face subdivisions of triangular grid graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• On operations preserving semi-transitive orientability of graphs
• New tools to study 1-11-representation of graphs
• Word-Representable Graphs: a Survey
• On word-representability of polyomino triangulations
• On semi-transitivity of (extended) Mycielski graphs
• Word-representable graphs from a word's perspective
• Word-representable graphs: orientations, posets, and bounds
• Semi-transitivity of directed split graphs generated by morphisms
• Computing shortest 12-representants of labeled graphs
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Alternation graphs
• On semi-transitive orientability of Kneser graphs and their complements
• Colourability and word-representability of near-triangulations
• Word-representability of split graphs
• On word-representable and multi-word-representable graphs
• Solving computational problems in the theory of word-representable graphs
• On semi-transitive orientability of split graphs
• On graphs representable by pattern-avoiding words

This page was built for publication: Semi-transitive orientations and word-representable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908303)