The edit distance of word-representable and comparability graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.18308
curl -X POST /api/v1/records/arxiv/2605.18308/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.18308/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'