О метрическом свойстве совершенных раскрасок

Аннотация

Для совершенных раскрасок доказано, что L_1 расстояние между двумя строками матрицы смежности графа не меньше, чем L_1 расстояние между соответствующими строками матрицы параметров раскраски. С помощью алгебраического подхода выведены следствия этого результата для совершенных 2-раскрасок и совершенных раскрасок графов расстояний l и дистанционно-регулярных графов. Также рассмотрены примеры бесконечных графов, для которых полученное свойство исключает из множества допустимых несколько матриц параметров совершенных раскрасок.