Boundedness and Separation in the Graph Covering Number Framework

For a graph class G and a graph H, the four G-covering numbers of H, namely global cngG(H), union cnᵤG(H), local cnₗG(H), and folded cnfG(H), each measure in a slightly different way how well H can be covered with graphs from G. For every G and H it holds \[ { cn}gG(H) ≥ { cn}ᵤG(H) ≥ { cn}ₗG(H) ≥ { cn}fG(H) \] and in general each inequality can be arbitrarily far apart. We investigate structural properties of graph classes G and H such that for all graphs H ∈ H, a larger G-covering number of H can be bounded in terms of a smaller G-covering number of H. For example, we prove that if G is hereditary and the chromatic number of graphs in H is bounded, then there exists a function f (called a binding function) such that for all H ∈ H it holds cnᵤG(H) ≤ f( cngG(H)). For G we consider graph classes that are component-closed, hereditary, monotone, sparse, or of bounded chromatic number. For H we consider graph classes that are sparse, M-minor-free, of bounded chromatic number, or of bounded treewidth. For each combination and every pair of G-covering numbers, we either give a binding function f or provide an example of such G,H for which no binding function exists.