On Languages Describing Large Graph Classes
This work provides a novel theoretical framework for graph representation, relevant to researchers in graph theory and formal languages, but the results are foundational rather than immediately applicable.
The paper introduces a new formalism for representing graph classes using formal binary languages, where words define edge patterns. It shows that languages like palindromes, copy-words, Lyndon words, and Dyck words can represent all graphs or specific graph classes, enabling new structural characterizations.
In this work, we introduce a new notion for representing graph classes with formal languages. In contrast to the seminal work by Kitaev and Pyatkin to represent graphs by words, we use formal binary languages in order to have a set of patterns (given by the languages' words) defining the edges in the graph. In particular, we investigate famous languages like the palindromes, copy-words, Lyndon words, and Dyck words to represent all graphs or specific graph classes by restricting these languages.