4-изящные деревья

Пусть $f$ — раскраска вершин связного графа $G$ в краски из множества красок $\{1, 2, \dots, k\}$. Раскраска $f$ на множестве ребер графа $G$ индуцирует функцию $f'(e) = |f(u) - f(v)|$, где $e = uv$ — произвольное ребро графа $G$. Число $f'(e)$ будем называть цветом ребра $e$, индуцированным раскраской $f$. Раскраска $f$ называется изящной $k$-раскраской графа $G$, если $f'$ является реберной раскраской этого графа. Граф будем называть $k$-изящным или, просто, изящным, если он обладает изящной $k$-раскраской. Основная цель нашей работы — дать два достаточных условия, каждое из которых гарантирует 4-изящность деревьев (см. теоремы 1 и 2). Кроме этого мы исследуем свойства 4-изящных графов для доказательства теорем 1 и 2. Найденные свойства мы также используем в следующих работах для изучения 4-изящных графов и 4-изящных деревьев в общем случае. Отметим, что 4-изящные деревья устроены достаточно сложно, а 3-изящные связные графы устроены очень просто. Они исчерпываются простыми цепями длины не более 3. Нетрудно установить, что любой 4-изящный граф не содержит вершин степени, большей 3. Поэтому мы рассматриваем деревья $T$, степени вершин которых не превосходят числа 3. Вершины степени 3 в дереве $T$ мы будем называть узлами. Будем говорить, что для двух узлов $u$ и $v$ дерева $T$ узловое расстояние между ними равно числу $t$, если существует простая цепь от $u$ до $v$, число внутренних вершин в которой равно $t\geq 1$ и все эти внутренние вершины имеют степень 2 в дереве $T$. Конечно, узловое расстояние определено не для каждой пары узлов. Среди прочих свойств 4-изящных графов установлено, что такие графы не содержат простых цепей, состоящих из трех узлов. Указанные нами достаточные условия 4-изящности деревьев состоят в запрете появления в них пар узлов, узловое расстояние между которыми равно 1 или 2.