{"id":"arxiv/2605.18308","url":"https://arxiv.org/abs/2605.18308","tags":["math.CO"],"score":0,"title":"The edit distance of word-representable and comparability graphs","domain":"math.CO","source":"arxiv","authors":["Sergey Kitaev","Ryan R. Martin"],"reviews":0,"subject":"math.CO","summary":"In this paper, we establish that the maximum edit distance of an $n$-vertex graph from the hereditary property of word-representable graphs is $n^2/8-o(n^2)$. In addition, we establish that the maximum edit distance of an $n$-vertex graph from the hereditary property of poset comparability graphs is $5n^2/32-o(n^2)$. In fact, we determine the edit distance function over all edge densities $p\\in [0,1]$ for the property of word-representable graphs, for the property of $k$-word-representable graphs for each $k\\geq 2$, and for the property comparability graphs. The latter has a peculiar…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-18","reactions":{}}