1 citations · 1 across the 10 of their papers we have counts for
14 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 Seymour…
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 cop…
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…
Twin-width one
Jungho Ahn, Hugo Jacob, Noleen Köhler +3
We investigate the structure of graphs of twin-width at most , and obtain the following results: - Graphs of twin-width at most are permutation graphs. In particular they ha…
Brooks-type colourings of digraphs in linear time
Daniel Gonçalves, Lucas Picasarri-Arrieta, Amadeus Reinald
Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lovász showed that su…
Oriented trees in -chromatic digraphs, a subquadratic bound for Burr's conjecture
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald
In 1980, Burr conjectured that every directed graph with chromatic number contains any oriented tree of order as a subdigraph. Burr showed that chromatic number $(k-1)^2…
The -binding function of -directional segment graphs
Lech Duraj, Ross J. Kang, Hoang La +4
Given a positive integer , the class -DIR is defined as all those intersection graphs formed from a finite collection of line segments in having at most s…
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of
Linda Cook, Tomáš Masařík, Marcin Pilipczuk +2
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph is -free if does not contain as an induced sub(di)graph. The…
Twin-width VI: the lens of contraction sequences
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +1
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…