This analysis shows how k-representable graphs connect to k-local word representations, implying further insights into their structure.
In this work, we investigate the relationship between k-repre\-sentable graphs and graphs representable by k-local words. In particular, we show that every graph representable by a k-local word is $(k+1)$-representable. A previous result about graphs represented by $1$-local words is revisited with new insights. Moreover, we investigate both classes of graphs w.r.t. hereditary and in particular the speed as a measure. We prove that the latter ones belong to the factorial layer and that the graphs in this classes have bounded clique-width.
No takes yet. Share an insight, caveat, or question.
Böll et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: