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

Свойства

Разреженность Согласно любой свободный от -бициклов граф с вершинами имеет рёбер, т.е. граф существенно более редкий, чем плотный граф. Эта работа рассматривает число рёбер свободных от биклик графов, но стандартное приложение вероятностного метода переносит те же границы на произвольные графы.. В обратную сторону, если семейство графов определено запрещёнными подграфами или замкнуто по отношению к операции взятия подграфа и не включает плотные графы произвольно большого размера, оно должно быть свободным от -биклик для некоторого , в противном случае, семейство должно включать произвольно большие плотные полные двудольные графы.

В качестве нижней границы Эрдёш, Хайнал и Муун высказали предположение, что любой максимальный свободный от -биклик двудольный граф (к которому нельзя добавить ребро без создания -биклики) имеет по меньшей мере рёбер, где и — число вершин на каждой из долей графа.

Связь с другими типами семейств разреженных графов Граф с вырождением является обязательно свободным от -биклик. Кроме того, семейство свободных от биклик графов должно быть нигде не плотным, что означает, что для любого числа существует граф, который не является -неглубоким минором какого-либо графа из семейства. В частности, если существует граф с вершинами, не являющийся 1-неглубокими минором, то семейство должно быть свободным от -биклик, поскольку все графы с вершинами являются 1-неглубокими минорами графа . Таким образом, свободные от биклик семейства графов унифицируют два из наиболее общих классов разреженных графов.

Приложения

Дискретная геометрия В комбинаторной геометрии многие типы графов инцидентности заведомо свободны от биклик. В качестве простого примера граф инцидентности конечного множества точек и прямых на евклидовой плоскости заведомо не содержит подграфа.

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

Примечания

Литература

. See in particular Lemma 3.1 and the remarks following the lemma.

Категория:Семейства графов