8 papers
-word--representable Graphs
Duncan Adamson, Amanita Dietz, Pamela Fleischmann +2
This paper investigates the new notion of -word--repre\-sentable graphs: the nodes of the graph correspond to the letters of the two words and there exists an edge between t…
(Sets of ) Complement Scattered Factors
Duncan Adamson, Pamela Fleischmann, Annika Huch
Starting in the 1970s with the fundamental work of Imre Simon, \emph{scattered factors} (also known as subsequences or scattered subwords) have remained a consistently and heavily…
Tight Bounds for the Number of Absent Subsequences
Duncan Adamson, Pamela Fleischmann, Annika Huch +3
A {\em subsequence} of a word is a word that can be obtained by deleting some letters from while maintaining the relative order of the remaining letters, e.g., $\mathtt…
Word Chain Generators for Prefix Normal Words
Duncan Adamson, Moritz Dudey, Pamela Fleischmann +1
In 2011, Fici and Lipták introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the pre…
Word-Representable Graphs and Locality of Words
Philipp Böll, Pamela Fleischmann, Annika Huch +4
In this work, we investigate the relationship between -repre\-sentable graphs and graphs representable by -local words. In particular, we show that every graph representable…
Jumbled Scattered Factors
Pamela Fleischmann, Annika Huch, Melf Kammholz +1
In this work, we combine the research on (absent) scattered factors with the one of jumbled words. For instance, is an absent scattered factor of $\mathtt{cauliflow…