Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by Petyuk and studied in the context of word-representability.

A universal cycle (u-cycle) for permutations of length n is a cyclic word, any size n window of which is order-isomorphic to exactly one permutation of length n , and all permutations of length n are covered. It is known that u-cycles for permutations exist, and they have been considered in the literature in several papers from different points of view. In this paper, we show how to construct a family of u-cycles for multi-dimensional permutations, which is based on applying an appropriate greedy algorithm . Our construction is a generalization of the greedy way by Gao et al. to construct u-cycles for permutations. We also note the existence of u-cycles for d -dimensional matrices.

A directed graph is semi-transitive if and only if it is acyclic and for any directed path u1→u2→⋯→ut, t≥2, either there is no edge from u1 to ut or all edges ui→uj exist for 1≤i

Tutte introduced planar maps in the 1960s in connection with what later became the celebrated Four-Color Theorem. A planar map is an embedding of a planar graph in the plane. Description trees, in particular, β-description trees, were introduced by Cori, Jacquard and Schaeffer in 1997, and they give a powerful tool to study planar maps. In this paper we introduce a relation on β-description trees and conjecture that this relation is a total order. Towards solving this conjecture, we provide an embedding of β(a,b)-trees into β(a−t,b+t)-trees for t≤a≤b+t, which is a far-reaching generalisation of an unpublished result of Claesson, Kitaev and Steingrímsson on embedding of β(1,0)-trees into β(0,1)-trees that gives a combinatorial proof of the fact that the number of rooted nonseparable planar maps with n+1 edges is more than the number of bicubic planar maps with 3n edges.

We introduce the notion of unavoidable (complete) sets of word patterns, which is a refinement for that of words, and study certain numerical characteristics for unavoidable sets of patterns. In some cases we employ the graph of pattern overlaps introduced in this paper, which is a subgraph of the de Bruijn graph and which we prove to be Hamiltonian. In other cases we reduce a problem under consideration to known facts on unavoidable sets of words. We also give a relation between our problem and the extensively studied universal cycles and prove that thereexists a universal cycle for word patterns of any length over any alphabet. The Stirling numbers of the second kind and the Möbius function appear in our results.