Orientations without forbidden patterns on three vertices
Research output: Contribution to journal › Research article › Contributed › peer-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 language | English |
---|---|
Article number | 128912 |
Journal | Applied mathematics and computation |
Volume | 480 |
Publication status | Published - 1 Nov 2024 |
Peer-reviewed | Yes |
Keywords
ASJC Scopus subject areas
Keywords
- Forb(F)-graph, Forbidden subgraph characterization, Generalized colouring, Graph homomorphism