PHOEG: an online tool for discovery and education in extremal graph theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912986664271872 |
|---|---|
| author | Bonte, Sébastien Devillez, Gauvain Dusollier, Valentin Mélot, Hadrien |
| author_facet | Bonte, Sébastien Devillez, Gauvain Dusollier, Valentin Mélot, Hadrien |
| contents | Extremal Graph Theory heavily relies on exploring bounds and inequalities between graph invariants, a task complicated by the rapid combinatorial explosion of graphs. Various tools have been developed to assist researchers in navigating this complexity, yet they typically rely on heuristic, probabilistic, or non-exhaustive methods, trading exactness for scalability. PHOEG takes a different stance: rather than approximating, it commits to an exact approach.
PHOEG is an interactive online tool (https://phoeg.umons.ac.be) designed to assist researchers and educators in graph theory. Building upon the exact geometrical approach of its predecessor, GraPHedron, PHOEG embeds graphs into a two-dimensional invariant space and computes their convex hull, where facets represent inequalities and vertices correspond to extremal graphs. PHOEG modernizes and expands this approach by offering a comprehensive web interface and API, backed by an extensive database of pairwise non-isomorphic graphs including all graphs up to order 10. Users can intuitively define invariant spaces by selecting a pair of invariants, apply constraints and colorations, visualize resulting convex polytopes, and seamlessly inspect the corresponding drawn graphs.
In this paper, we detail the software architecture and new web-based features of PHOEG. Furthermore, we demonstrate its practical value in two primary contexts: in research, by illustrating its ability to quickly identify conjectures or counterexamples to conjectures, and in education, by detailing its integration into university-level coursework to foster student discovery of classical graph theory principles. Finally, this paper serves as a brief survey of the extremal results and conjectures established over the past two decades using this geometric approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27242 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PHOEG: an online tool for discovery and education in extremal graph theory Bonte, Sébastien Devillez, Gauvain Dusollier, Valentin Mélot, Hadrien Combinatorics Discrete Mathematics Extremal Graph Theory heavily relies on exploring bounds and inequalities between graph invariants, a task complicated by the rapid combinatorial explosion of graphs. Various tools have been developed to assist researchers in navigating this complexity, yet they typically rely on heuristic, probabilistic, or non-exhaustive methods, trading exactness for scalability. PHOEG takes a different stance: rather than approximating, it commits to an exact approach. PHOEG is an interactive online tool (https://phoeg.umons.ac.be) designed to assist researchers and educators in graph theory. Building upon the exact geometrical approach of its predecessor, GraPHedron, PHOEG embeds graphs into a two-dimensional invariant space and computes their convex hull, where facets represent inequalities and vertices correspond to extremal graphs. PHOEG modernizes and expands this approach by offering a comprehensive web interface and API, backed by an extensive database of pairwise non-isomorphic graphs including all graphs up to order 10. Users can intuitively define invariant spaces by selecting a pair of invariants, apply constraints and colorations, visualize resulting convex polytopes, and seamlessly inspect the corresponding drawn graphs. In this paper, we detail the software architecture and new web-based features of PHOEG. Furthermore, we demonstrate its practical value in two primary contexts: in research, by illustrating its ability to quickly identify conjectures or counterexamples to conjectures, and in education, by detailing its integration into university-level coursework to foster student discovery of classical graph theory principles. Finally, this paper serves as a brief survey of the extremal results and conjectures established over the past two decades using this geometric approach. |
| title | PHOEG: an online tool for discovery and education in extremal graph theory |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.27242 |