Covering Numbers in Theory and Practice

• Applicant: Privatdozent Dr. Torsten Ueckerdt
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 520723789

Graph colorings or decompositions and, more generally, coverings are the most classical problems in graph theory and combinatorics. We mostly seek to minimize the number of colors, that is, the total number of parts in a covering, while the concrete problem statement determines which subgraphs of the given graph are accepted as parts in a valid covering. Together with a colleague, I initiated in 2016 the formalization of a framework that unifies notations and techniques from the numerous variants of covering problems in the field, including proper vertex colorings, edge colorings, Ramsey numbers, splitting numbers, vertex cover numbers, graph homomorphisms, arboricities, boxicities, and graph factors; just to name a few. We introduced global, union, local, and folded covering numbers with respect to an arbitrary guest class containing all acceptable parts in a covering. This subsumes numerous existing covering and coloring problems and enabled us to find and utilize connections between existing covering numbers, as well as to identify the most relevant open problems in several fields. Particularly, the local covering numbers have since then already received a lot of attention in different communities of mathematics and computer science, for example by our introduction of local poset dimension, local graph boxicity, and local page number over the past years. In this project the covering number framework shall be extended, enhanced, and utilized. It consists of six research topics, devoted to fundamental characteristics, algorithmic aspects, sparse graphs, interval graphs, induced and ordered variants, and applications in practice. While each topic offers some promising directions to pursue with concrete open problems and goals, the overall project shall continue the development of the theory of covering numbers, both in very general and very specific settings. By conducting high-quality research and talks at major conferences with strong results and fruitful connections, the four different covering numbers --global, union, local, and folded-- shall be advertised even more prominently in the scientific community and bring the development of graph theory forward.

• DFG Programme: Research Grants