Обобщение локально ограниченных графов ширины

17

Известен ли следующий класс графов в литературе?

Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dTграммзнак равно(В,Е)vВграммdvграммT

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

Серж Гасперс
источник

Ответы:

11

Концепция использования свойств, которыми граф обладает локально, может быть взята еще дальше. Давар, Гроэ и Кройцер в Локально исключая минор рассматривал классы графов, которые локально исключают минор, а Дворжак, Крал и Томас в Решении свойств первого порядка для разреженных графов рассматривали классы графов, которые имеют (локально) ограниченное расширение.

Оба эти класса относятся к классам нигде не плотных графов, введенных Несетриль и Оссона де Мендес.

Grohe объявил на этой неделе на конференции Highlights, что Grohe, Kreutzer и Siebertz. доказали, что каждое свойство графов, определяемых в логике первого порядка, может быть решено за почти линейное время на нигде не плотных классах графов. Это подразумевает множество результатов проходимости с фиксированными параметрами на нигде не плотных графах, например, для (связного) доминирующего множества и ядра орграфа (оба параметризованы размером решения), дерева Штейнера (параметризованного размера дерева) и выполнимости схемы ( параметризованный глубиной контура и весом решения по Хэммингу).

Себастьян Сибертц
источник
9

Это не совсем то, о чем вы просите, но это очень тесно связано и, следовательно, может быть тем не менее интересным для вас:

Концепция локальной ширины дерева, введенная в M. Frick, M.Grohe, Определение свойств первого порядка локально разложимых по дереву структур, является более общей, чем определение локальной ширины дерева в статье в Википедии, на которую вы ссылаетесь. Для каждого графа , то локальная древесная ширина из является функцией , которая отображает радиус до максимальной древесной ширины из среди всех вершин из , где является подграфом индуцируется вершинами на расстоянии не более отграммграммLTвесграммрNрграмм(v)vграммNрграмм(v)граммрvеLTвесграмм(р)е(р)рграмм

ФХ
источник
1
Действительно, это кажется более общим, чем определение в Википедии. Однако, если требуется, чтобы класс графов был закрыт под индуцированными подграфами, оба определения эквивалентны. Обратите внимание, что статья Фрика-Гроэ также упоминается в статье Википедии.
Серж Гасперс