the archive
#graph classes
2 resultscs.DS2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
The paper establishes polynomial‑time algorithms for Feedback Vertex Set, Odd Cycle Transversal and their connected variants on (sP1+P3)-free graphs and cographs, and shows NP‑comp…
#cycle transversal#feedback vertex set#odd cycle transversal#connected variants
cs.DS2019
On low rank-width colorings
O-joung Kwon, MichaÅ Pilipczuk, Sebastian Siebertz
The paper defines low rank‑width colorings, a generalization of low tree‑depth colorings, and investigates which graph classes admit such colorings, proving positive results for po…
#low rank-width colorings#graph classes#bounded expansion#graph powers