Cross

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

Given a bipartite graph $B = (U \cup V,E)$, two non-adjacent edges $e,e'\in E$ with $e = (u_{1},v_{1})$ and $e' = (u_{2},v_{2})$ are said to form a cross if $(u_{1},v_{2}) \in E$ and $(u_{2},v_{1}) \in E$. 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 $B$ is a set of edges $E' \subseteq E$ with the property that no two edges $e,e' \in E'$ are cross-adjacent. A cross-free coloring of $B$ is a coloring of the edge set $E$ subject to the restriction that no pair of cross-adjacent edges has the same color.

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

Литература

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