2020/12/23 by Santiago Guzmán‐Pro, Guzmán-Pro, Santiago, César Hernández‐Cruz +1
Computer Science · Engineering · Mathematics · #05C15 #05C60 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.12811
openalex publication_date 2020/12/23 · openalex created_date 2022/07/25 · openalex updated_date 2026/08/01
Several graph properties are characterized as the class of graphs that admit an orientation avoiding finitely many oriented structures. For instance, if Fk is the set of homomorphic images of the directed path on k+1 vertices, then a graph is k-colourable if and only if it admits an orientation with no induced oriented graph in Fk. There is a fundamental question underlying this kind of characterizations: given a graph property, P, is there a finite set of oriented graphs, F, such that a graph belongs to P if and only if it admits an orientation with no induced oriented graph in F? We address this question by exhibiting necessary conditions upon certain graph classes to admit such a characterization. Consequently, we exhibit an uncountable family of hereditary classes, for which no such finite set exists. In particular, the class of graphs with no holes of prime length belongs to this family.