Cross

Cross — скрещивание.

Given a bipartite graph [math]\displaystyle{ B = (U \cup V,E) }[/math], two non-adjacent edges [math]\displaystyle{ e,e'\in E }[/math] with [math]\displaystyle{ e = (u_{1},v_{1}) }[/math] and [math]\displaystyle{ e' = (u_{2},v_{2}) }[/math] are said to form a cross if [math]\displaystyle{ (u_{1},v_{2}) \in E }[/math] and [math]\displaystyle{ (u_{2},v_{1}) \in E }[/math]. Two edges are said to be cross-adjacent if either they are adjacent (i.e. share a common node) or they form a cross. A cross-free matching in [math]\displaystyle{ B }[/math] is a set of edges [math]\displaystyle{ E' \subseteq E }[/math] with the property that no two edges [math]\displaystyle{ e,e' \in E' }[/math] are cross-adjacent. A cross-free coloring of [math]\displaystyle{ B }[/math] is a coloring of the edge set [math]\displaystyle{ E }[/math] subject to the restriction that no pair of cross-adjacent edges has the same color.

The cross-chromatic index, [math]\displaystyle{ \chi^{\ast}(B) }[/math], of [math]\displaystyle{ B }[/math] is the minimum number of colors required to get a cross-free coloring of [math]\displaystyle{ B }[/math]. The cross-free matching number of [math]\displaystyle{ B }[/math], [math]\displaystyle{ m^{\ast}(B) }[/math], is defined as the edge cardinality of the maximum cross-free matching in [math]\displaystyle{ B }[/math].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.