8 papers
Forbidding anticomplete planar minors: Induced ErdÅs--Pósa property and Maximum Independent Set in QP
Maria Chudnovsky, Amadeus Reinald, Stéphan Thomassé
The ErdÅs--Pósa theorem asserts that every graph with no disjoint cycles contains a set of vertices such that has no cycle. Robertson and Seymou…
Induced ErdÅs--Pósa property for long holes, long thetas, and beyond
Jadwiga Czyżewska, Tomáš MasaÅÃk, Marcin Pilipczuk +2
The induced ErdÅs--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all c…
Dynamic Detours
Daniel Dadush, MichaÅ Pilipczuk, Amadeus Reinald +2
Fix a parameter . We give dynamic data structures that for a fully dynamic undirected graph , updated over time by edge insertions and edge deletions, can answe…
Inversion diameter and 2-edge-colored homomorphisms
Carmen Arana, Thomas Bellitto, Hector Buffière +3
In an oriented graph, the inversion of a subset of vertices X is the operation reversing the direction of every arc with both endpoints in X. Given a graph G, the inversion distanc…
Plane Strong Connectivity Augmentation
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald +1
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph can be augmented with (any num…
Making an oriented graph acyclic using inversions of bounded or prescribed size
Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch +3
Given an oriented graph , the inversion of a subset of vertices consists in reversing the orientation of all arcs with both endpoints in . When the subset is of size…