Orientations without forbidden patterns on three vertices

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer128912
FachzeitschriftApplied mathematics and computation
Jahrgang480
PublikationsstatusVeröffentlicht - 1 Nov. 2024
Peer-Review-StatusJa

Schlagworte

Schlagwörter

  • Forb(F)-graph, Forbidden subgraph characterization, Generalized colouring, Graph homomorphism