$3$-регулярные подграфы и $(3,1)$-раскраски $4$-регулярных псевдографов

Пусть $G$ – $4$-регулярный псевдограф. Назовём $(3,1)$-раскраской графа $G$ раскраску его рёбер в несколько цветов такую, что в каждой вершине сходятся три ребра одного цвета и одно – другого. Свойства $(3,1)$-раскрасок тесно связаны с наличием в графе $3$-регулярных подграфов. В работе доказывается, что любой связный $4$-регулярный псевдограф, содержащий $3$-регулярный подграф, обладает $(3,1)$-раскраской. Кроме того, любой $4$-регулярный псевдограф без кратных рёбер (но, возможно, с петлями) обладает $(3,1)$-раскраской, что служит косвенным подтверждением предположения (недоказанного), что любой такой граф содержит $3$-регулярный подграф. В работе также проводится анализ вопроса о том, какое наименьшее количество цветов необходимо для $(3,1)$-раскраски данного $4$-регулярного графа. В заключение доказывается, что наличие $(3,1)$-раскраски, удовлетворяющей дополнительным требованиям (упорядоченной $(3,1)$-раскраски), удовлетворяющей дополнительным требованиям, равносильно наличию $3$-регулярного подграфа. Ил. 8, библиогр. 20.