2020/03/12 by Santiago Guzmán‐Pro, Guzmán-Pro, Santiago, César Hernández‐Cruz +1
Computer Science · Mathematics · #05C15 #05C60 #05C75 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2003.05606
openalex publication_date 2020/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 P3 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.