Covering minimal separators and potential maximal cliques in P-t-free graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438233" target="_blank" >RIV/00216208:11320/21:10438233 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9R_k4NwTjC" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9R_k4NwTjC</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37236/9473" target="_blank" >10.37236/9473</a>

Result language
angličtina
Original language name
Covering minimal separators and potential maximal cliques in P-t-free graphs
Original language description
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 not well-undestood. 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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GJ19-04113Y" target="_blank" >GJ19-04113Y: Advanced tools in combinatorics, topology and related areas</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)