Covering minimal separators and potential maximal cliques in P_t-free graphs
share
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 ≥ 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.
READ FULL TEXT