Uogólnienie lokalnych wykresów szerokości

Czy w literaturze znana jest następująca klasa grafów?

Klasa wykresów parametryzowany dodatnimi liczbami całkowitymi i T i zawiera co wykres G = ( V , E ), tak, że dla każdego wierzchołka v ∈ V The podgrafu z G wywołane na wszystkich wierzchołków w odległości co najwyżej d z V w G ma szerokość co najwyżej t .$d$$t$$G=(V,E)$$v\in V$$G$$d$$v$$G$$t$

Uogólnia pojęcie lokalnie ograniczonej szerokości i wydaje się przydatne podczas wyszukiwania lokalnych struktur na wykresach.

Koncepcja wykorzystania właściwości lokalnie posiadanych przez wykres może być jeszcze bardziej rozwinięta. Dawar, Grohe i Kreutzer w Lokalnie wyłączeniem Minor uważane klas grafów, które lokalnie wykluczają małoletni i Dvoraka, Kral i Thomas w Decydując właściwości pierwszego rzędu dla nielicznych wykresów rozważanych klas grafów, które (lokalnie) ograniczonych ekspansję.

Obie te klasy są uwzględnione przez klasy nigdzie gęstych grafów, wprowadzone przez Nesetrila i Ossona de Mendez.

Grohe ogłosił w tym tygodniu na konferencji Highlights, że Grohe, Kreutzer i Siebertz. udowodnili, że każdą właściwość grafów definiowalną w logice pierwszego rzędu można rozwiązać w prawie liniowym czasie na nigdzie gęstych klasach grafów. To implikuje wiele wyników pomiaru parametrów stałych na nigdzie gęstych wykresach, np. Dla (połączonego) dominującego zestawu i jądra digrafa (oba sparametryzowane wielkością rozwiązania), drzewa Steiner'a (sparametryzowanego rozmiarem drzewa) i satysfakcji obwodu ( sparametryzowane przez głębokość obwodu i masę Hamminga roztworu).

Nie jest to dokładnie to, o co prosisz, ale jest bardzo blisko powiązane, a zatem może być dla ciebie interesujące:

$G$$G$$ltw^G$$r$$N^G_r(v)$$v$$G$$N^G_r(v)$$G$$r$$v$$f$$ltw^G(r) \leq f(r)$ dla każdego $r$ i każdy wykres $G$ należący do klasy.