Решение задачи об описательной сложности изоморфизма подграфа с помощью кнезеровских графов

В работе изучается задача нахождения наименьшего числа переменных формулы первого порядка, записывающей свойство input-графа содержать подграф, изоморфный заданному pattern-графу. Рассматриваются input-графы, имеющие достаточно большую связность. Ранее эта задача была решена для всех pattern-графов с 4 вершинами, кроме двух – простого цикла и diamond-графа. В настоящей работе мы нашли значение этой величины для двух оставшихся графов.
Библиография: 8 названий.