6 papers · 1 filter
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…
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…
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 s…