О правильных $3$-раскрасках ребер кубического графа

В работе изучаются определяющие множества рёбер кубического графа (то есть, множества рёбер, $3$-раскраска которых однозначно задает правильную $3$-раскраску всех рёбер графа). В кубическом графе с $3n$ рёбрами доказано существование определяющего множества из $n$ рёбер. В трёхсвязном кубическом плоском графе с $3n$ рёбрами, каждая грань которого имеет не более чем $d$ вершин, доказано существование определяющего множества из не более чем $n - {n-2d+3\over 3d-8}$ ребер. В обоих случаях описан алгоритм построения определяющего множества. Для связного кубического графа с $3n$ рёбрами строится такая серия многочленов над $\mathbb F_3$ от $ n+1$ переменных, что отличие от тождественного $0$ любого из них эквивалентно наличию правильной 3-раскраски рёбер. В заключение статьи доказывается, что связный кубический мультиграф $G$ на $2n$ вершинах имеет не более чем $3\cdot 2^n$ правильных $3$-раскрасок рёбер. Эта оценка – точная. В случае, когда $G$ имеет не более чем одну пару кратных рёбер, доказано, что $G$ имеет не более чем $9\cdot 2^{n-2}$ правильных $3$-раскрасок рёбер. Библ. – 6 назв.