Ahmed Ghazy and Tim Hartmann, Continuous Graphs – An Overview and a Coloring Problem

We consider a continuous model of graphs, introduced by Dearing and Francis in 1974, where each edge of G to be a unit interval, giving rise to an infinite metric space that contains not only the vertices of G but all points on all edges of G. Several standard graph problems can be defined and studied on continuous graphs, yielding many surprising algorithmic results and combinatorial connections.

The motivation can be exemplified by the well-known Independent Set problem on graphs. Given a graph G, we want to place k facilities that are pairwise at least a distance 2 edge lengths apart. In some applications, such as when the underlying graph represents a street network, it is reasonable to allow placing a facility not only at a crossroad but also somewhere within a street, that is, not only at a vertex but also at any point on an edge between two vertices. This motivates the study of the Independent Set problem on continuous graphs. In such a setting, for example, the problem corresponds to requiring pairwise distance r=2 for the placed facilities. However, we may also study the problem where we fix r to any positive integer, rational, or even irrational number. Other problems studied in the continuous model include Dominating Set, TSP, and Coloring.

In the first part of this talk, we will give a general overview of research on continuous graphs and computational problems in this setting.

In the second part, we explore, as part of recent work, a coloring problem on continuous graphs akin to the well-known Hadwiger-Nelson Problem.

Based on joint work with Fabian Frei, Florian Hörsch, Tom Janßen, Stefan Lendl, Dániel Marx, Prahlad Narasimhan, and Gerhard Woeginger.