Я перешел по ссылке в вопросе, и сокращение там фактически приводит к графам, ребра которых имеют естественную окраску, так что каждый Kn На графике присутствует «радуга» Kn"(имеет ровно одно ребро каждого цвета). Другими словами, мы можем легко отрегулировать уменьшение в этой бумаге так, чтобы оно сводилось к вашей проблеме, а не уменьшалось до разбиения на Kns проблема: просто назначьте каждому ребру цвет в соответствии с этой естественной раскраской, и тогда график можно будет разбить на «радугу» Kns "тогда и только тогда, когда он может быть разбит на Knс на всех.
Базовая структура сокращения в этой статье может быть выполнена с помощью следующих 3 шагов:
- Создайте много копий определенного графика Hn,p,
- Определите определенные части некоторых копий Hn,p друг с другом (т.е. объединить вершины / ребра между несколькими различными копиями Hn,p).
- Удалите определенные вершины / ребра из некоторых копий.
График Hn,p имеет в качестве своих вершин множество длиныn векторы по модулю p для которого компоненты добавляют к 0 модификация p, Ребра соединяют каждые две вершины, которые отличаются только двумя компонентами с разницей+1 а также −1 в этих двух компонентах.
Я предлагаю следующую раскраску для этого графика: назначьте цвет каждому ребру в соответствии с его направлением. Еслиx а также y смежные вершины, то x−y вектор с n−2 компоненты, равные 0один компонент равен 1 и один компонент равен −1, Другими словами, для каждого края(x,y) есть (n2) варианты для каких компонентов x−yненулевые Если мы назначим уникальный цвет для каждой из этих опций, то у нас будет раскраска для всех ребер, так что у каждого ребра в одном и том же направлении будет одинаковый цвет. Довольно легко проверить, что вKn в Hn,pв том же направлении. Поэтому каждыйKn в Hn,p это радуга Kn под эту раскраску.
Когда мы следуем за сокращением, мы используем эту раскраску для каждой копии Hn,p, Поэтому в конце шага 1 в приведенном выше списке каждыйKn на графике радуга Kn,
На шаге 2 приведенного выше списка мы идентифицируем некоторые вершины / ребра друг с другом. В частности, в сокращении мы всегда определяемKn с другим Kn, Но в этой ситуации (где всеKnс из копии Hn,p) каждый Kn это либо перевод "стандарт Kn«который называет газета K или перевод −K, Поэтому мы либо идентифицируем две параллельныеKnс или два Knс "сальто" друг от друга. В любом случае, края, которые идентифицированы по двумKns параллельны и поэтому имеют одинаковый цвет. Например, см. Рисунок 2 в документе; идентифицированные ребра всегда параллельны. Таким образом, поскольку мы никогда не пытаемся идентифицировать два ребра разных цветов, раскраска в конце шага 1 в приведенном выше списке может быть естественным образом превращена в раскраску в конце шага 2. Идентификация некоторых вершин / ребер вместе не создает любой новыйKnс, так что в конце этого шага все еще Kn это радуга Kn,
Наконец, в шаге 3 мы удаляем некоторые вершины / ребра, которые также не создают новых Kns. Таким образом, у нас есть желаемое свойство: под цвет, который я указал, каждыйKn на графике, созданном этим сокращением, есть радуга Kn,