Orientations without forbidden patterns on three vertices
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
Given a set F of oriented graphs, a graph G is a Forbe(F)-graph if it admits an F-free orientation. Skrien showed that proper-circular arc graphs, nested interval graphs and comparability graphs, correspond to Forbe(F)-graph classes for some set F of orientations of P3. Building on these results, we exhibit the list of all Forbe(F)-graph classes when F is a set of oriented graphs on three vertices. Structural characterizations for these classes are provided, except for the so-called perfectly-orientable graphs and the transitive-perfectly-orientable graphs, which remain as open problems.
Details
Originalsprache | Englisch |
---|---|
Aufsatznummer | 128912 |
Seitenumfang | 16 |
Fachzeitschrift | Applied mathematics and computation |
Jahrgang | 480 (2024) |
Publikationsstatus | Veröffentlicht - 1 Juli 2024 |
Peer-Review-Status | Ja |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Forb(F)-graph, Forbidden subgraph characterization, Generalized colouring, Graph homomorphism