Том 15, номер 1, 2008 г., Стр. 11-16

УДК 519.172
О. В. Бородин, И. Г. Дмитриев, A. O. Иванова
Высота цикла длины 4 в 1-планарных графах с минимальной степенью 5 без треугольников

Аннотация:
Граф называется 1-планарным, если его можно изобразить на плоскости так, чтобы каждое ребро скрещивалось не более чем с одним другим ребром. Известно, что в 1-планарном графе есть вершина степени не больше 7, а также либо вершина степени не больше 4, либо цикл длины не больше 4. Доказывается, что 1-планарный граф без треугольников и вершин степени не меньше 5 содержит цикл длины 4, состоящий из вершин степени не больше 8.
Библ. 8.

О. В. Бородин ¹
И. Г. Дмитриев ²
A. O. Иванова ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Якутский государственный университет им. М. К. Аммосова, Институт математики и информатики,
ул. Кулаковского, 48, 677000 Якутск, Россия
е-mail: brdnoleg@math.nsc.ru, mf_igd@mail.ru, shmgnanna@mail.ru

Статья поступила 24 декабря 2007 г.