Том 21, номер 5, 2014 г., Стр. 3-16

УДК 519.174
Бернштейн А. Ю.
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-регулярного подграфа.
Ил. 9, библиогр. 20.

Ключевые слова: 4-регулярный граф, рёберная раскраска.

Бернштейн Антон Юрьевич ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: bahtoh@gmail.com

Статья поступила 16 декабря 2013 г.
Исправленный вариант — 21 февраля 2014 г.

Литература

[1] Дистель Р. Теория графов. - Новосибирск: Изд-во Ин-та математики, 2002. - 336 c.

[2] Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. - М.: Мир, 1988. - 430 c.

[3] Ташкинов В. А. 3-Однородные части 4-однородных графов // Мат. заметки. - 1984. - T. 36, №2. - С. 239–259.

[4] Addario-Berry L., Dalal K., Reed B. A. Degree constrained subgraphs // Discrete Appl. Math. - 2008. - Vol. 156, N7. - P. 1168–1174.

[5] Alon N., Friedland S., Kalai G. Regular subgraphs of almost regular graphs // J. Comb. Theory. Ser. B. - 1984. - Vol. 37, N1. - P. 79–91.

[6] Alon N., Friedland S., Kalai G. Every 4-regular graph plus an edge contains a 3-regular subgraph // J. Comb. Theory. Ser. B. - 1984. - Vol. 37, N1. - P. 92–93.

[7] Alon N. Combinatorial Nullstellensatz // J. Comb. Probab. Comput. - 1999. - Vol. 8, N1–2. - P. 7–29.

[8] Berge C., Las Vergnas M. On the existence of subgraphs with degree constraints // Indagationes Mathematicae (Proc.). - 1978. - Vol. 81, N1. - P. 165–176.

[9] Bondy J. A., Murty U. S. R. Graph theory. - Berlin: Springer-Verl., 2008. - 655 p. (Grad. Texts Math.; Vol.244).

[10] Chvátal V., Fleischner H., Sheehan J., Thomassen C. Three-regular subgraphs of four-regular graphs // J. Graph Theory. - 1979. - Vol. 3, N4. - P. 371–386.

[11] Cornuéjols G. General factors of graphs // J. Comb. Theory. Ser. B. - 1988. - Vol. 45, N2. - P. 185–198.

[12] Heinrich K., Hell P., Kirkpatrick D. G., Liu G. A simple existence criterion for (g < f)-factors // Discrete Math. - 1990. - Vol. 85, N3. - P. 313–317.

[13] Kano M., Saito A. [a, b]-Factors of graphs // Discrete Math. - 1983. - Vol. 47. - P. 113–116.

[14] Kano M. Factors of regular graphs // J. Comb. Theory. Ser. B. - 1986. - Vol. 41, N1. - P. 27–36.

[15] Lovґasz L. Subgraphs with prescribed valencies // J. Comb. Theory. - 1970. - Vol. 8, N4. - P. 391–416.

[16] Moreno O., Zinoviev V. A. Some sufficient conditions for 4-regular graphs to have 3-regular subgraphs // Lect. Notes Comput. Sci. - 1994. - Vol. 781. - P. 164–171.

[17] Moreno O., Zinoviev V. A. Three-regular subgraphs of four-regular graphs // Eur. J. Comb. - 1998. - Vol. 19, N3. - P. 369–373.

[18] Olson J. E. A combinatorial problem on finite Abelian groups. II // J. Number Theory. - 1969. - Vol. 1, N2. - P. 195–199.

[19] Sebö A. General antifactors of graphs // J. Comb. Theory. Ser. B. - 1993. - Vol. 58, N2. - P. 174–184.

[20] Tutte W. T. The subgraph problem // Ann. Discrete Math. - 1978. - Vol. 3. - P. 289–295.