2026/07/21 by Miriam Goetze, Lucas Schwebler
#math.CO
The global and local G-covering number cgG(H) and clG(H) encode how well the edges of a graph H can be covered with graphs from a graph class G: in the global setting, we minimize the number of graphs from G required, in the local setting how often a vertex is hit by the graphs of the cover. Within this work we consider for G the graph classes B of all bipartite and Bc of all complete bipartite graphs. We give a tight lower bound on clB(H) in terms of the fractional chromatic number of H, thereby giving a local analogue of a result by Harary, Hsu and Miller. Answering a question by Fishburn and Hammer, we show that it is NP-hard to determine cl^Bc(H). Further, we provide a finite and monotone graph class G such that cgG(H) can be computed in constant time for every graph H while determining clG(H) is NP-hard. This yields a natural example to a question raised by Knauer and Ueckerdt.