English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A graph is called $P_t$-free} if it does not contain a $t$-vertex path as aninduced subgraph. While $P_4$-free graphs are exactly cographs, the structureof $P_t$-free graphs for $t \geq 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 algorithmsfor MWIS in $P_6$-free graphs~[SODA 2019] and $3$-Coloring in $P_7$-freegraphs~[Combinatorica 2018] have been found only recently. In both cases, thealgorithms 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~[SODA2014] and in $P_6$-free graphs~[SODA 2019] is the so-called Separator CoveringLemma that asserts that every minimal separator in the graph can be covered bythe union of neighborhoods of a constant number of vertices. In this note weshow 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 coveringpotential maximal cliques with unions of neighborhoods.

Covering minimal separators and potential maximal cliques in $P_t$-free graphs