Stéphan Thomassé
YOU?
Author Swipe
View article: Two-block paths in oriented graphs of large semidegree
Two-block paths in oriented graphs of large semidegree Open
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish…
View article: Graphs without a 3-Connected Subgraph are 4-Colourable
Graphs without a 3-Connected Subgraph are 4-Colourable Open
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colourable. We show that the number 5 of colours can be replaced by 4, which is best possible.
View article: Lollipops, dense cycles and chords
Lollipops, dense cycles and chords Open
In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\geq 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}…
View article: A Polynomial-Time Approximation Algorithm for Complete Interval Minors
A Polynomial-Time Approximation Algorithm for Complete Interval Minors Open
As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is…
View article: ($\overrightarrow{P_6}$, triangle)-Free Digraphs Have Bounded Dichromatic Number
($\overrightarrow{P_6}$, triangle)-Free Digraphs Have Bounded Dichromatic Number Open
The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichr…
View article: Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring Open
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequenc…
View article: A structural description of Zykov and Blanche Descartes graphs
A structural description of Zykov and Blanche Descartes graphs Open
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph created using Zykov's construction. We give a structural ch…
View article: On the complexity of Client-Waiter and Waiter-Client games
On the complexity of Client-Waiter and Waiter-Client games Open
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular after Erdos and Selfridge's first result on their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these g…
View article: Twin-width and permutations
Twin-width and permutations Open
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomass\'e, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been fur…
View article: Twin-Width IV: Ordered Graphs and Matrices
Twin-Width IV: Ordered Graphs and Matrices Open
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model the…
View article: Graphs without a 3-connected subgraph are 4-colorable
Graphs without a 3-connected subgraph are 4-colorable Open
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible.
View article: Dichromatic Number and Cycle Inversions
Dichromatic Number and Cycle Inversions Open
The results of this note were stated in the first author PhD manuscript in 2006 but never published. The writing of a proof given there was slightly careless and the proof itself scattered across the document, the goal of this note is to g…
View article: Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems
Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems Open
We study the notion of k-stabilizer universal quantum state, that is, an n-qubit quantum state, such that it is possible to induce any stabilizer state on any k qubits, by using only local operations and classical communications. These sta…
View article: On the Limits of Information Spread by Memory-Less Agents
On the Limits of Information Spread by Memory-Less Agents Open
We address the self-stabilizing bit-dissemination problem, designed to capture the challenges of spreading information and reaching consensus among entities with minimal cognitive and communication capacities. Specifically, a group of n ag…
View article: Temporalizing Digraphs via Linear-Size Balanced Bi-Trees
Temporalizing Digraphs via Linear-Size Balanced Bi-Trees Open
In a directed graph D on vertex set v₁,… ,v_n, a forward arc is an arc v_iv_j where i < j. A pair v_i,v_j is forward connected if there is a directed path from v_i to v_j consisting of forward arcs. In the Forward Connected Pairs Problem (…
View article: Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 cup C_4
Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 cup C_4 Open
International audience
View article: Lossy Kernelization for (Implicit) Hitting Set Problems
Lossy Kernelization for (Implicit) Hitting Set Problems Open
We re-visit the complexity of kernelization for the $d$-Hitting Set problem. This is a classic problem in Parameterized Complexity, which encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feed…
View article: Factoring Pattern-Free Permutations into Separable ones
Factoring Pattern-Free Permutations into Separable ones Open
We show that for any permutation $π$ there exists an integer $k_π$ such that every permutation avoiding $π$ as a pattern is a product of at most $k_π$ separable permutations. In other words, every strict class $\mathcal C$ of permutations …
View article: Extremal Independent Set Reconfiguration
Extremal Independent Set Reconfiguration Open
The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on inde…
View article: Twin-width and permutations
Twin-width and permutations Open
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been furth…
View article: A tamed family of triangle-free graphs with unbounded chromatic number
A tamed family of triangle-free graphs with unbounded chromatic number Open
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in th…
View article: Temporalizing digraphs via linear-size balanced bi-trees
Temporalizing digraphs via linear-size balanced bi-trees Open
In a directed graph $D$ on vertex set $v_1,\dots ,v_n$, a \emph{forward arc} is an arc $v_iv_j$ where $i0$ such that one can always find an enumeration realizing $c.|R|$ forward connected pairs $\{x_i,y_i\}$ (in either direction).
View article: Bounded twin-width graphs are polynomially $χ$-bounded
Bounded twin-width graphs are polynomially $χ$-bounded Open
We show that every graph with twin-width $t$ has chromatic number $O(ω^{k_t})$ for some integer $k_t$, where $ω$ denotes the clique number. This extends a quasi-polynomial bound from Pilipczuk and Sokołowski and generalizes a result for bo…
View article: Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$ Open
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when $H$ is any planar…
View article: ( #» P 6 , triangle)-free digraphs have bounded dichromatic number
( #» P 6 , triangle)-free digraphs have bounded dichromatic number Open
The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichr…
View article: Extremal Independent Set Reconfiguration
Extremal Independent Set Reconfiguration Open
The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on inde…
View article: An Improved Kernelization Algorithm for Trivially Perfect Editing
An Improved Kernelization Algorithm for Trivially Perfect Editing Open
In the Trivially Perfect Editing problem one is given an undirected graph G = (V,E) and an integer k and seeks to add or delete at most k edges in G to obtain a trivially perfect graph. In a recent work, Dumas et al. [Dumas et al., 2023] p…
View article: Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication
Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication Open
We continue developing the theory around the twin-width of totally ordered binary structures (or equivalently, matrices over a finite alphabet), initiated in the previous paper of the series. We first introduce the notion of parity and lin…
View article: Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication
Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication Open
We continue developing the theory around the twin-width of totally ordered binary structures (or equivalently, matrices over a finite alphabet), initiated in the previous paper of the series. We first introduce the notion of parity and lin…