Том 21, номер 2, 2014 г., Стр. 33–51

УДК 519.8
Глебов А. Н., Замбалаева Д. Ж.
Разбиение плоского графа с обхватом 6 на два леса с длиной цепей не больше 4

Аннотация:
Доказано, что множество вершин любого плоского графа с обхватом не менее 6 можно разбить на два подмножества, каждое из которых порождает лес, в котором длина любой цепи не превосходит 4. 
Ил. 7, библиогр. 9.

Ключевые слова: плоский граф, обхват, путевая разбиваемость.

Глебов Алексей Николаевич ^1,2
Замбалаева Долгор Жамьяновна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru, dolgor@ngs.ru

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

Литература

[1] Бородин О. В., Иванова А. О. Почти правильные 2-раскраски вершин разреженных графов // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, №2. - С. 16–20.
Borodin O. V., Ivanova A. O. Near-proper vertex 2-colorings of sparse graphs // J. Appl. Industr. Math. - 2010. - Vol. 4, N1. - P. 21-23.

[2] Бородин О. В., Иванова А. О. Разбиение разреженных плоских графов на два подграфа малой степени // Сиб. электрон. мат. изв. - 2009. - Т. 6. - С. 13–16.

[3] Глебов А. Н., Замбалаева Д. Ж. Путевые разбиения планарных графов // Сиб. электрон. мат. изв. - 2007. - Т. 4. - С. 450–459.

[4] Замбалаева Д. Ж. Разбиение плоского графа с обхватом 7 на два звёздных леса // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 3. - С. 20–46.

[5] Borodin O., Ivanova A. List strong linear 2-arboricity of sparse graphs // J. Graph Theory. - 2011. - Vol. 67, N2. - P. 83–90.

[6] Borowiecki M., Broere I., Frick M., Mihok P., Semanisin G. A survey of hereditary properties of graphs // Discus. Math., Graph Theory. - 1997. - Vol. 17, N 1. - P. 5–50.

[7] Broere I., Dorfling M., Dunbar J. E., Frick M. A path(ological) partition problem // Discus. Math., Graph Theory. - 1998. - Vol. 18, N 1. - P. 113–125.

[8] Broere I., Hajnal P., Mihok P., Semanisin G. Partition problems and kernels of graphs // Discus. Math., Graph Theory. - 1997. - Vol. 17, N 2. - P. 311–313.

[9] Mihok J. Additive hereditary properties and uniquely partitionable graphs //Graphs, hypergraphs and matroids. - Zielona Gora: Higher College of Engineering, 1985. - P. 49–58.