Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909709676576768 |
|---|---|
| author | Grigoriev, Alexander Faulkner, Katherine |
| author_facet | Grigoriev, Alexander Faulkner, Katherine |
| contents | Inspired by notorious combinatorial optimization problems on graphs, in this paper we consider a series of related problems defined using a metric space and topology determined by a graph. Particularly, we present the Independent Set, Vertex Cover, Chromatic Number and Treewidth problems on, so-called, continuous or metric graphs where every edge is represented by a unit-length continuous interval rather than by a pair of vertices. If any point of any unit-interval edge is considered as a possible member of a hitting set or a cover, the classical combinatorial problems become trickier and many open questions arise. Notably, in many real-life applications, such a continuous view of a graph is more natural than the classic combinatorial definition of a graph. The contribution of this paper is twofold: i) we survey the known results for optimization problems on continuous graphs, and ii) we create a list of open problems related to the continuous graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14554 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems Grigoriev, Alexander Faulkner, Katherine Combinatorics Discrete Mathematics 05C99 (Primary) 05C85 (Secondary) Inspired by notorious combinatorial optimization problems on graphs, in this paper we consider a series of related problems defined using a metric space and topology determined by a graph. Particularly, we present the Independent Set, Vertex Cover, Chromatic Number and Treewidth problems on, so-called, continuous or metric graphs where every edge is represented by a unit-length continuous interval rather than by a pair of vertices. If any point of any unit-interval edge is considered as a possible member of a hitting set or a cover, the classical combinatorial problems become trickier and many open questions arise. Notably, in many real-life applications, such a continuous view of a graph is more natural than the classic combinatorial definition of a graph. The contribution of this paper is twofold: i) we survey the known results for optimization problems on continuous graphs, and ii) we create a list of open problems related to the continuous graphs. |
| title | Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems |
| topic | Combinatorics Discrete Mathematics 05C99 (Primary) 05C85 (Secondary) |
| url | https://arxiv.org/abs/2501.14554 |