{"id":"arxiv/2607.18833","url":"https://arxiv.org/abs/2607.18833","tags":["math.CO"],"score":0,"title":"On the Computational Complexity of Local and Global Covering Numbers","domain":"math.CO","source":"arxiv","authors":["Miriam Goetze","Lucas Schwebler"],"reviews":0,"subject":"math.CO","summary":"The global and local $\\mathcal{G}$-covering number $c_{\\mathrm{g}}^{\\mathcal{G}}(H)$ and $c_{\\mathrm{l}}^{\\mathcal{G}}(H)$ encode how well the edges of a graph $H$ can be covered with graphs from a graph class $\\mathcal{G}$: in the global setting, we minimize the number of graphs from $\\mathcal{G}$ required, in the local setting how often a vertex is hit by the graphs of the cover. Within this work we consider for $\\mathcal{G}$ the graph classes $\\mathcal{B}$ of all bipartite and $\\mathcal{B}_{\\mathrm{c}}$ of all complete bipartite graphs. We give a tight lower bound on…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}