The Generic Circular Triangle-Free Graph
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
In this article, we introduce the generic circular triangle-free graph (Formula presented.) and propose a finite axiomatization of its first-order theory. In particular, our main results show that a countable graph (Formula presented.) embeds into (Formula presented.) if and only if it is a (Formula presented.) -free graph. As a byproduct of this result, we obtain a geometric characterisation of finite (Formula presented.) -free graphs, and the (finite) list of minimal obstructions of unit Helly circular-arc graphs with independence number strictly less than three. The circular chromatic number (Formula presented.) is a refinement of the classical chromatic number (Formula presented.). We construct (Formula presented.) so that a graph (Formula presented.) has a circular chromatic number strictly less than three if and only if (Formula presented.) maps homomorphically to (Formula presented.). We build on our main result to show that (Formula presented.) if and only if (Formula presented.) can be extended to a (Formula presented.) -free graph, and in turn, we use this result to reprove an old characterisation of (Formula presented.) due to Brandt (1999). Finally, we answer a question recently asked by Guzmán-Pro, Hell, and Hernández-Cruz by showing that the problem of deciding for a given finite graph (Formula presented.) whether (Formula presented.) is NP-complete.
Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 4 |
| Seiten (von - bis) | 426-445 |
| Seitenumfang | 20 |
| Fachzeitschrift | Journal of Graph Theory |
| Jahrgang | 109 |
| Ausgabenummer | 4 |
| Publikationsstatus | Veröffentlicht - Aug. 2025 |
| Peer-Review-Status | Ja |
Externe IDs
| Scopus | 105000474114 |
|---|---|
| ORCID | /0000-0001-8228-3611/work/208071907 |
Schlagworte
Schlagwörter
- homomorphisms, circular chromatic number, circular-arc graphs, infinite graphs, computational complexity