Orientations without forbidden patterns on three vertices

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

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

Original languageEnglish
Article number128912
JournalApplied mathematics and computation
Volume480
Publication statusPublished - 1 Nov 2024
Peer-reviewedYes

Keywords

Keywords

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