Clément Rambaud
YOU?
Author Swipe
View article: Structures of graph classes and of their excluded minors
Structures of graph classes and of their excluded minors Open
Une classe de graphes est dite close par mineur si elle est close par suppressions d'arêtes, suppressions de sommets, et contractions d'arêtes. Les classes de graphes closes par mineur jouent un rôle central en théorie des graphes grâce à …
View article: The Grid-Minor Theorem Revisited
The Grid-Minor Theorem Revisited Open
We prove that for every planar graph X of treedepth h , there exists a positive integer c such that for every X -minor-free graph G , there exists a graph H of treewidth at most f ( h ) such that G is isomorphic to a subgraph of $$H\boxtim…
View article: Faithful universal graphs for minor-closed classes
Faithful universal graphs for minor-closed classes Open
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed…
View article: Problems, Proofs, and Disproofs on the Inversion Number
Problems, Proofs, and Disproofs on the Inversion Number Open
The inversion of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. The inversion number of an oriented graph $D$, denoted by $\text{inv}(D)$, is the minimum number of inversions …
View article: Weak coloring numbers of minor-closed graph classes
Weak coloring numbers of minor-closed graph classes Open
International audience
View article: Centered colorings in minor-closed graph classes
Centered colorings in minor-closed graph classes Open
A vertex coloring $φ$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$, either $φ$ uses more than $p$ colors on $H$, or there is a color that appears exactly once on $H$. We prove that for every fixed positive inte…
View article: Blow-ups and extensions of trees in tournaments
Blow-ups and extensions of trees in tournaments Open
A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not …
View article: On the minimum number of arcs in 4‐dicritical oriented graphs
On the minimum number of arcs in 4‐dicritical oriented graphs Open
The dichromatic number of a digraph is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph is ‐dicritical if and each proper subdigraph of satisfies …
View article: Weak coloring numbers of minor-closed graph classes
Weak coloring numbers of minor-closed graph classes Open
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-mi…
View article: On the Minimum Number of Arcs in \(\boldsymbol{k}\)-Dicritical Oriented Graphs
On the Minimum Number of Arcs in \(\boldsymbol{k}\)-Dicritical Oriented Graphs Open
International audience
View article: Diameter of the inversion graph
Diameter of the inversion graph Open
In an oriented graph $\vec{G}$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The inversion graph of a labelled graph $G$, denoted by ${\mathcal{I}}(G)$, is the gr…
View article: Quickly excluding an apex-forest
Quickly excluding an apex-forest Open
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 20…
View article: Subdivisions in dicritical digraphs with large order or digirth
Subdivisions in dicritical digraphs with large order or digirth Open
Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subdigr…
View article: On the minimum number of inversions to make a digraph k-(arc-)strong
On the minimum number of inversions to make a digraph k-(arc-)strong Open
The inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D(X). We study sinv k (D) (resp. sinv k (D) which is the minimum number of inversions needed to transform D into a k-arc-strong (resp. k…
View article: The Grid-Minor Theorem Revisited
The Grid-Minor Theorem Revisited Open
International audience
View article: The $χ$-binding function of $d$-directional segment graphs
The $χ$-binding function of $d$-directional segment graphs Open
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easil…
View article: The grid-minor theorem revisited
The grid-minor theorem revisited Open
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of …
View article: On the minimum number of arcs in $4$-dicritical oriented graphs
On the minimum number of arcs in $4$-dicritical oriented graphs Open
The dichromatic number $\vecχ(D)$ of a digraph $D$ is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph $D$ is $k$-dicritical if $\vecχ(D) = k$ and…
View article: Neighborhood complexity of planar graphs
Neighborhood complexity of planar graphs Open
Reidl, Sánchez Villaamil, and Stravopoulos (2019) characterized graph classes of bounded expansion as follows: A class $\mathcal{C}$ closed under subgraphs has bounded expansion if and only if there exists a function $f:\mathbb{N} \to \mat…
View article: On the minimum number of inversions to make a digraph k-(arc-)strong
On the minimum number of inversions to make a digraph k-(arc-)strong Open
The {\it inversion} of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. We study $\sinv'_k(D)$ (resp. $\sinv_k(D)$) which is the minimum number of inversions needed to transform…
View article: Problems, proofs, and disproofs on the inversion number
Problems, proofs, and disproofs on the inversion number Open
The {\it inversion} of a set $X$ of vertices in a digraph $D$ consists in reversing the direction of all arcs of $D\langle X\rangle$. The {\it inversion number} of an oriented graph $D$, denoted by ${\rm inv}(D)$, is the minimum number of …
View article: Preference swaps for the stable matching problem
Preference swaps for the stable matching problem Open
An instance I of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in I is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a …
View article: On the parameterized complexity of symmetric directed multicut
On the parameterized complexity of symmetric directed multicut Open
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is t…
View article: On the minimum number of arcs in $k$-dicritical oriented graphs
On the minimum number of arcs in $k$-dicritical oriented graphs Open
The dichromatic number $\dic(D)$ of a digraph $D$ is the least integer $k$ such that $D$ can be partitioned into $k$ directed acyclic digraphs. A digraph is $k$-dicritical if $\dic(D) = k$ and each proper subgraph $D'$ of $D$ satisfies $\d…
View article: On the Dichromatic Number of Surfaces
On the Dichromatic Number of Surfaces Open
In this paper, we give bounds on the dichromatic number $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\…