Edges covered by k vertex neighborhoods

Question 2.1 · arXiv:2102.10220

arXiv Question high confidence— first stated 2021-03-19

Authors: Jacob Fox, Zoe Himwich, Nitya Mani

Status open high confidence

Question 2.1 from arXiv:2102.10220 asks how many edges of a graph $G$ can be covered by the union of $k$ vertex neighborhoods, formalised via $u(G,k)$ and $m(n,k) = \min_G(e(G)-u(G,k))$. The paper itself proves bounds on $m(n,k)$ as a tool for upper bounds on $h(n,k,H)$, but the general question is explicitly left open. No subsequent paper resolving or substantially advancing Question 2.1 was found in the indexed literature as of May 2026. The source paper appeared in the Journal of Graph Theory in 2023.

Reviewer notes. No follow-up paper addressing Question 2.1 was found after a wide web search (3 searches + 3 fetches). The conjecture is recent (2021, published 2023) and the absence of follow-up is consistent with status open with high confidence. The internal reference arXiv:2105.03956 is unrelated to this question and should be disregarded.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Given a graph $G$, how many edges of $G$ can we cover by the union of $k$ neighborhoods of vertices of $G$?

Context

The authors define $u(G,k)$ as the maximum number of edges covered by the union of $k$ vertex neighborhoods and study $m(n,k) = \min_G(e(G) - u(G,k))$. Bounds on this quantity are the main tool for proving upper bounds on $h(n,k,H)$ when $H$ is a clique or an odd wheel.

Source paper

Making an $H$-Free Graph $k$-Colorable
Jacob Fox, Zoe Himwich, Nitya Mani · 2021-03-19
https://arxiv.org/abs/2102.10220 PDF source