The Generic Circular Triangle-Free Graph

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer4
Seiten (von - bis)426-445
Seitenumfang20
FachzeitschriftJournal of Graph Theory
Jahrgang109
Ausgabenummer4
PublikationsstatusVeröffentlicht - Aug. 2025
Peer-Review-StatusJa

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