论文标题
图形属性的定向表达式
Oriented expressions of graph properties
论文作者
论文摘要
几种图形属性被描述为避免有限多个方向结构的方向的图形类别。例如，如果$ f_k $是$ k+1 $ vertices上有向路径的一组同构图像，则当且仅当它在$ f_k $中没有诱导的图形的方向时，图形为$ k $ - 颜色。这种特征是一个基本问题：给定图形属性，$ \ Mathcal {p} $，是否有一组有限的方向图，$ f $，以便图形属于$ \ MATHCAL {p} $，并且只有在$ f $ $ f $中的方向上属于方向时，只有在$ f $中的方向？我们通过在某些图类别上表现出必要条件来承认这种特征来解决这个问题。因此，我们展示了一个无数的遗传阶级家庭，为此，没有这种有限的集合。特别是，没有质量长度孔的图形类别属于这个家族。
Several graph properties are characterized as the class of graphs that admit an orientation avoiding finitely many oriented structures. For instance, if $F_k$ 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 $F_k$. There is a fundamental question underlying this kind of characterizations: given a graph property, $\mathcal{P}$, is there a finite set of oriented graphs, $F$, such that a graph belongs to $\mathcal{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.
