arXiv
Open Access
2020
Orientations without forbidden patterns on three vertices
Santiago Guzmán-Pro
César Hernández-Cruz
Abstrak
Given a set $F$ of oriented graphs, a graph $G$ is an $F$-graph if it admits an $F$-free orientation. Building on previous work by Bang-Jensen and Urrutia, we propose a master algorithm that determines if a graph admits an $F$-free orientation when $F$ is a subset of the orientations of $P_3$ and the transitive triangle. We extend previous results of Skrien by studying the class of $F$-graphs, when $F$ is any set of oriented graphs of order three. Structural characterizations for all such sets are provided, except for the so-called perfectly-orientable graphs and one of its subclasses, which remain as open problems.
Penulis (2)
S
Santiago Guzmán-Pro
C
César Hernández-Cruz
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2020
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓