Том 4, серия 1, номер 4, 1997 г., Стр. 3-5

УДК 519.17
С. В. Августинович
О разбиении множества ребер графа на изоморфные деревья

Аннотация:
Пусть $G$ – произвольный $k$-однородный двудольный граф, ребра которого можно правильно раскрасить в $k$ цветов так, что в каждом его цикле найдутся четыре ребра, на раскраску которых потрачено не более двух цветов. Доказано, что для всякого дерева $T$ c $k$ ребрами существует разбиение множества ребер графа $G$ на индуцированные подграфы, каждый из которых изоморфен дереву $T$.
Библиогр. 2.

Августиноеич С. В. ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: avgust@math.nsc.ru

Статья поступила 1 августа 1997 г.