Three ways to cover a graph

We consider the problem of covering an input graph  HH with graphs from a fixed covering class  GG. The classical covering number of HH with respect to GG is the minimum number of graphs from GG needed to cover the edges of HH without covering non-edges of HH. We introduce a unifying notion of three covering parameters with respect to GG, two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures “how far” HH is from GG in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, e.g., interval graphs and planar graphs, the local covering number has received little attention.We provide new bounds on each covering number with respect to the following covering classes: linear forests, star forests, caterpillar forests, and interval graphs. The classical graph parameters that result this way are interval number, track number, linear arboricity, star arboricity, and caterpillar arboricity. As input graphs we consider graphs of bounded degeneracy, bounded degree, bounded tree-width or bounded simple tree-width, as well as outerplanar, planar bipartite, and planar graphs. For several pairs of an input class and a covering class we determine exactly the maximum ordinary, local, and folded covering number of an input graph with respect to that covering class.