Wykresy, w których każdy minimalny separator jest niezależnym zestawem

Tło: Niech będą dwoma wierzchołkami niekierowanego wykresu G = ( V , E ) . Zestaw wierzchołek S ⊆ V jest U , V -separator jeżeli U i V , należą do różnych połączonych składników G - S . Jeśli żaden odpowiedni podzbiór separatora u , v S nie jest separatorem u , v, wówczas S jest minimalnym u , $u, v$$G=(V,E)$$S\subseteq V$$u,v$$u$$v$$G-S$$u,v$$S$$u,v$$S$$u,v$-separator. Zestaw wierzchołków jest (minimalnym) separatorem, jeśli istnieją wierzchołki u , v takie, że S jest (minimalnym) separatorem u , v .$S\subseteq V$$u, v$$S$$u,v$

Dobrze znane twierdzenie G. Diraca stwierdza, że ​​wykres nie ma indukowanych cykli długości co najmniej czterech (zwanych grafem triangulowanym lub akordowym) wtedy i tylko wtedy, gdy każdy z jego minimalnych separatorów jest kliką. Dobrze wiadomo również, że wykresy triangulowane można rozpoznać w czasie wielomianowym.

Moje pytania: na jakich wykresach każdy minimalny separator jest niezależnym zbiorem? Czy te wykresy są badane? Jaka jest złożoność rozpoznawania tych wykresów? Przykłady takich wykresów obejmują drzewa i cykle.

Twoje wykresy zostały scharakteryzowane przez ten artykuł http://arxiv.org/pdf/1103.2913.pdf .

Edycja: W powyższym artykule udowodniono, że wykresy, w których każdy minimalny separator jest niezależnym zestawem, są dokładnie tymi, które nie zawierają cyklu z dokładnie jednym akordem.

Wykresy nie zawierające cyklu z dokładnie jednym akordem zostały dogłębnie zbadane przez Trotignon i Vuskovic, Twierdzenie o strukturze wykresów bez cyklu z unikalnym akordem i jego konsekwencjami , J. Graph Theory 63 (2010) 31-67 DOI . W wyniku tego artykułu wykresy te można rozpoznać w czasie wielomianowym. (Jednak w tym dokumencie nie wskazano związku z niezależnymi minimalnymi separatorami!)

Edycja (17 września 2013 r.): Bardzo niedawno (patrz tutaj ) Terry Mckee opisuje wszystkie wykresy, na których każdy minimalny separator wierzchołków jest kliką lub niezależnym zestawem. Okazuje się, że są to „sumy brzegowe” wykresów akordowych i wykresów, w których każdy minimalny separator wierzchołków jest niezależnym zestawem.

Najwyraźniej najwcześniejsza charakterystyka wykresów, w których każdy minimalny separator jest niezależnym zestawem, pojawiła się w TA McKee, „Niezależne wykresy separatora”, Utilitas Mathematica 73 (2007) 217--224. Są to dokładnie wykresy, na których żaden cykl nie ma unikalnego akordu (lub równoważnie, na którym w każdym cyklu każdy akord ma akord krzyżujący się).

Są dwa nowe artykuły na wykresach bez cyklu z dokładnie jednym akordem. Oba dotyczą głównie kolorowania tych wykresów: http://arxiv.org/abs/1309.2749 i http://arxiv.org/abs/1311.1928 .

$O(m^2n)$$O(mn)$