Semi-transitive orientations and word-representable graphs

DOI10.1016/j.dam.2015.07.033zbMath1329.05217arXiv1501.07108OpenAlexW1767557960MaRDI QIDQ908303

Magnús M. Halldórsson, Sergey Kitaev, Artem V. 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)

Related Items (15)

Word-representability of split graphs generated by morphisms ⋮ Word-representability of triangulations of grid-covered cylinder graphs ⋮ Word-Representable Graphs: a Survey ⋮ Representing split graphs by words ⋮ Word-representability of face subdivisions of triangular grid graphs ⋮ On semi-transitive orientability of Kneser graphs and their complements ⋮ On word-representable and multi-word-representable graphs ⋮ The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group ⋮ On semi-transitive orientability of split graphs ⋮ On operations preserving semi-transitive orientability of graphs ⋮ An embedding technique in the study of word-representability of graphs ⋮ On graphs representable by pattern-avoiding words ⋮ Solving computational problems in the theory of word-representable graphs ⋮ On the representation number of a crown graph ⋮ Word-representability of Toeplitz graphs

Cites Work

• Unnamed Item
• Circle graphs and monadic second-order logic
• Word problem of the Perkins semigroup via directed acyclic graphs.
• On the complexity of diagram testing
• On scheduling cycle shops: Classification, complexity and approximation
• Enumerating split-pair arrangements
• Alternation Graphs
• The Hardness of Approximating Poset Dimension
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Graphs Capturing Alternations in Words
• The Complexity of the Partial Order Dimension Problem
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• On representable graphs

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