Oriented expressions of graph properties
Por:
Guzman-Pro, Santiago, Hernandez-Cruz, Cesar
Publicada:
1 oct 2022
Resumen:
Several graph properties are characterized as a class of graphs that
admit an orientation avoiding a finite set of 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 subgraph 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 subgraph in F? We address this question by exhibiting
some necessary conditions upon certain graph classes for them 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. (c) 2022 Elsevier Ltd. All rights reserved.
Filiaciones:
Guzman-Pro, Santiago:
Univ Nacl Autonoma Mexico, Fac Ciencias, Ave Univ 3000, Circuito Exterior S-N,Ciudad Univ, Mexico City 04510, Mexico
Hernandez-Cruz, Cesar:
Univ Nacl Autonoma Mexico, Fac Ciencias, Ave Univ 3000, Circuito Exterior S-N,Ciudad Univ, Mexico City 04510, Mexico
Green Submitted
|