Alternation graphs

DOI10.1007/978-3-642-25870-1_18MaRDI QIDQ3104776zbMATH OpenOpenAlexFDO

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

Publication date 16 December 2011

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25870-1_18

zbMATH Keywords

alternation numberword representation of a graph

Mathematics Subject Classification ID

Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Semi-transitive orientations and word-representable graphs
• A comprehensive introduction to the theory of word-representable graphs
• Word-representability of split graphs
• Word-Representable Graphs: a Survey
• On representable graphs

Cites work

• A study of the cyclic scheduling problem on parallel processors
• Circle graphs and monadic second-order logic
• Enumerating split-pair arrangements
• Graph Classes: A Survey
• Graph Drawing
• Graphs Capturing Alternations in Words
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• On representable graphs
• On scheduling cycle shops: Classification, complexity and approximation
• 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

(25)

• Alternating graphs
• On semi-transitive orientability of Kneser graphs and their complements
• On strict (outer-)confluent graphs
• On operations preserving semi-transitive orientability of graphs
• Solving computational problems in the theory of word-representable graphs
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• New results on word-representable graphs
• Word-Representable Graphs: a Survey
• Representing graphs via pattern avoiding words
• On strict (outer-)confluent graphs
• On word-representable and multi-word-representable graphs
• Minimum length word-representants of word-representable graphs
• Word-representability of graphs with respect to split recomposition
• Word-representable graphs from a word's perspective
• Characterization of double-arborescences and their minimum length word-representants
• On semi-transitive orientability of circulant graphs
• Compact distributed certification of geometric graph classes
• On semi-transitive orientability of triangle-free graphs
• From word-representable graphs to altered Tverberg-type theorems
• Word-representation numbers of graphs: bottlenecks and bounds
• On word-representability of minimal non-comparability graphs
• Word-representable co-bipartite graphs: representation number, speed, and entropy
• On word-representability of polyomino triangulations
• Semi-transitive orientations and word-representable graphs

This page was built for publication: Alternation graphs

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