For a graph class $\mathcal G$ and a graph $H$, the four $\mathcal G$-covering numbers of $H$, namely global ${ \rm cn}_{ g}^{ \mathcal{ G}}(H)$, union ${ \rm cn}_{ u}^{ \mathcal{ G}}(H)$, local ${ \rm cn}_{ l}^{ \mathcal{ G}}(H)$, and folded ${ \rm cn}_{ f}^{ \mathcal{ G}}(H)$, each measure in a slightly different way how well $H$ can be covered with graphs from $\mathcal G$. For every $\mathcal G$ and $H$ it holds \[ { \rm cn}_{ g}^{ \mathcal{ G}}(H) \geq { \rm cn}_{ u}^{ \mathcal{ G}}(H) \geq { \rm cn}_{ l}^{ \mathcal{ G}}(H) \geq { \rm cn}_{ f}^{ \mathcal{ G}}(H) \] and in general each inequality can be arbitrarily far apart. We investigate structural properties of graph classes $\mathcal G$ and $\mathcal H$ such that for all graphs $H \in \mathcal{ H}$, a larger $\mathcal G$-covering number of $H$ can be bounded in terms of a smaller $\mathcal G$-covering number of $H$. For example, we prove that if $\mathcal G$ is hereditary and the chromatic number of graphs in $\mathcal H$ is bounded, then there exists a function $f$ (called a binding function) such that for all $H \in \mathcal{ H}$ it holds ${ \rm cn}_{ u}^{ \mathcal{ G}}(H) \leq f({ \rm cn}_{ g}^{ \mathcal{ G}}(H))$. For $\mathcal G$ we consider graph classes that are component-closed, hereditary, monotone, sparse, or of bounded chromatic number. For $\mathcal 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 $\mathcal G$-covering numbers, we either give a binding function $f$ or provide an example of such $\mathcal{ G},\mathcal{ H}$ for which no binding function exists.
Categories: math.CO cs.DM