Geodesic
Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
Andrzej Grzesik1 ; Tereza Klimošová2 ; Marcin Pilipczuk3 ; Michał Pilipczuk3
1Jagiellonian University
2Charles University
3University of Warsaw
The electronic journal of combinatorics, Tome 28 (2021) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph is called $P_t$-free if it does not contain a $t$-vertex path as an induced subgraph. While $P_4$-free graphs are exactly cographs, the structure of $P_t$-free graphs for $t \geqslant 5$ remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and $3$-Coloring are not known to be NP-hard on $P_t$-free graphs for any fixed $t$. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in $P_6$-free graphs~[SODA 2019] and $3$-Coloring in $P_7$-free graphs~[Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in $P_5$-free graphs~[SODA 2014] and in $P_6$-free graphs~[SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to $P_7$-free graphs and is false in $P_8$-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.
DOI : 10.37236/9473
Classification : 05C69, 05C70, 05C75, 05C85, 68R10
Mots-clés : maximum weight independent set, separator covering lemma

Andrzej Grzesik  1   ; Tereza Klimošová  2   ; Marcin Pilipczuk  3   ; Michał Pilipczuk  3

1 Jagiellonian University
2 Charles University
3 University of Warsaw 
@article{10_37236_9473,
     author = {Andrzej Grzesik and Tereza Klimo\v{s}ov\'a and Marcin Pilipczuk and Micha{\l} Pilipczuk},
     title = {Covering minimal separators and potential maximal cliques in {\(P_t\)-free} graphs},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {1},
     doi = {10.37236/9473},
     zbl = {1458.05194},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9473/}
}
TY  - JOUR
AU  - Andrzej Grzesik
AU  - Tereza Klimošová
AU  - Marcin Pilipczuk
AU  - Michał Pilipczuk
TI  - Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9473/
DO  - 10.37236/9473
ID  - 10_37236_9473
ER  - 
%0 Journal Article
%A Andrzej Grzesik
%A Tereza Klimošová
%A Marcin Pilipczuk
%A Michał Pilipczuk
%T Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9473/
%R 10.37236/9473
%F 10_37236_9473
Andrzej Grzesik; Tereza Klimošová; Marcin Pilipczuk; Michał Pilipczuk. Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9473

Cité par Sources :