Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski
The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…
cs.DS2026
On the complexity of edge subdivision to -free graphs
Marta Piecyk, R. B. Sandeep
Subdividing an edge in a graph replaces it by a path with one new vertex. For a graph , the \textsc{-free Subdivision} problem asks whether, given a graph an…
cs.DS2021
Faster 3-coloring of small-diameter graphs
Michał Dębski, Marta Piecyk, Paweł Rzążewski
We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for -vertex diameter-2 graphs this problem can be solved in su…