Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadically dependent} if the class of all graphs cannot be interpreted in its vertex-colored members using a fixed first-order formula. We prove two structural consequences of monadic dependence. First, every monadically dependent class has \emph{almost linear neighborhood complexity}: for every graph $G$ in the class and every set $A\subseteq V(G)$, the family $\{N_G(v)\cap A : v\in V(G)\}$ has size $|A|^{1+o(1)}$.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.10941
curl -X POST /api/v1/records/arxiv/2607.10941/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.10941/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'