Монохромный треугольник

В теории графов и теоретической информатике задача об одноцветном треугольнике — это алгоритмическая задача на графах, в которой цель состоит в том, чтобы разбить ребра заданного графа на два подграфа без треугольников . Она является NP-полной , но поддается решению с фиксированными параметрами на графах ограниченной древовидной ширины .

Задача монохроматического треугольника принимает в качестве входных данных неориентированный граф G(V,E) с множеством узлов V и множеством ребер E. Выходными данными является логическое значение, true, если множество ребер E графа G можно разбить на два непересекающихся множества E1 и E2, так что оба подграфа G1(V,E1) и G2(V,E2) являются графами без треугольников , и false в противном случае. Эта задача принятия решений является NP-полной . ^[1]

Проблему можно обобщить до раскраски ребер без треугольников , найдя назначение цветов ребрам графа так, чтобы ни один треугольник не имел всех трех ребер одного цвета. Задача об одноцветном треугольнике является частным случаем раскраски ребер без треугольников, когда доступно ровно два цвета. Если существует двухцветная раскраска ребер без треугольников, то ребра каждого цвета образуют два множества E1 и E2 задачи об одноцветном треугольнике. И наоборот, если задача об одноцветном треугольнике имеет решение, мы можем использовать один цвет для E1 и второй цвет для E2, чтобы получить раскраску ребер без треугольников.

По теореме Рамсея , для любого конечного числа k цветов существует число n такое, что полные графы с n или более вершинами не имеют раскрасок ребер без треугольников с k цветами. Для k  = 2 соответствующее значение n равно 6. То есть ответ на задачу об одноцветном треугольнике на полном графе K ₆ — нет.

Несложно выразить задачу монохроматического треугольника в монадической логике второго порядка графов (MSO ₂ ) с помощью логической формулы, которая утверждает существование разбиения ребер на два подмножества, таких, что не существует трех смежных вершин, все ребра которых принадлежат одной стороне разбиения. Из теоремы Курселя следует , что задача монохроматического треугольника является фиксированно-параметрически решаемой на графах ограниченной древовидной ширины . Точнее, существует алгоритм для решения задачи, время выполнения которого равно числу вершин входного графа, умноженному на быстрорастущую, но вычислимую функцию древовидной ширины. ^[2]