On Finding Directed Trees with Many Leaves (2009)
Daligault, Jean, Thomasse, Stephan
The Rooted Maximum Leaf Outbranching problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version...
Partitions versus sets : a case of duality (2009)
Lyaudet, Laurent, Mazoit, Frédéric, Thomasse, Stephan
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in...
Partitions versus sets : a case of duality (2009)
Lyaudet, Laurent, Mazoit, Frédéric, Thomasse, Stephan
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in...
Partitions versus sets : a case of duality (2009)
Lyaudet, Laurent, Mazoit, Frédéric, Thomasse, Stephan
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in...
A Polynomial Kernel for Multicut in Trees (2009)
Bousquet, Nicolas, Daligault, Jean, Thomasse, Stephan, Yeo, Anders
The {sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests....
Submodular Partition Functions (2009)
Amini, Omid, Mazoit, Frédéric, Nisse, Nicolas, Thomasse, Stephan
Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble-number of a graph and its tree-width. Our approach is based on a new definition of...
Submodular Partition Functions (2009)
Amini, Omid, Mazoit, Frédéric, Nisse, Nicolas, Thomasse, Stephan
Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble-number of a graph and its tree-width. Our approach is based on a new definition of...
Partitions versus sets : a case of duality (2009)
Lyaudet, Laurent, Mazoit, Frédéric, Thomasse, Stephan
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in...
Partitions versus sets : a case of duality (2009)
Lyaudet, Laurent, Mazoit, Frédéric, Thomasse, Stephan
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in...
On Finding Directed Trees with Many Leaves (2009)
Daligault, Jean, Thomasse, Stephan
The Rooted Maximum Leaf problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there...
On Finding Directed Trees with Many Leaves (2009)
Daligault, Jean, Thomasse, Stephan
The Rooted Maximum Leaf problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there...
Grundy Sets of Partial Orders. (2008)
Walter Deuber, Stephan Thomasse
Two players I and II are playing the Hackendot game, a slight variant of Hackenbush (see Berlekamp, Conway and Guy [1]) played on a partially ordered set P : First I chooses x 2 P and deletes the...
The Hoàng-Reed Conjecture holds for tournaments (2008)
Havet, Frederic, Thomasse, Stephan, Yeo, Anders
See pdf
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
The Hoàng-Reed Conjecture holds for tournaments (2008)
Havet, Frederic, Thomasse, Stephan, Yeo, Anders
See pdf
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
Frederic Havet, Stephan Thomasse
We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighbourhood is as large as its rst outneighbourhood.
The Categorical Product of two 5-chromatic digraphs can be 3-chromatic (2007)
Stephane Bessy, Stephan Thomasse, Bernard Lyon, Avenue Tony Garnier
We provide an example of a 5-chromatic oriented graph D such that the categorical product of D and TT5 is 3-chromatic, where TT5 is the transitive tournament on 5 vertices.
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
Complexity of $(p,1)$-total labelling (2007)
Havet, Frederic, Thomasse, Stephan
A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $\{0,\dots ,l\}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The...
Complexity of $(p,1)$-total labelling (2007)
Havet, Frederic, Thomasse, Stephan
A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $\{0,\dots ,l\}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The...
Total Domination of Graphs and Small Transversals of Hypergraphs (2007)
Thomasse, Stephan, Yeo, Anders
The main result of this paper is that every 4-uniform hypergraph on $n$ vertices and $m$ edges has a transversal with no more than $(5n+4m)/21$ vertices. In the particular case $n=m$, the transversal...
Spanning a strong digraph by $\alpha$ circuits: A proof of Gallai's conjecture. (2007)
Bessy, Stéphane, Thomasse, Stephan
In 1963, Tibor Gallai~\cite{TG} asked whether every strongly connected directed graph $D$ is spanned by $\alpha$ directed circuits, where $\alpha$ is the stability of $D$. We give a proof of this...
Partitions and orientations of the Rado graph (2007)
Diestel, Reinhard, Leader, Imre, Scott, Alex, Thomasse, Stephan
We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs...
Paths with two blocks in n-chromatic digraphs (2007)
Thomasse, Stephan, Havet, Frederic, Addario-Berry, Louigi
We show that every oriented path of order n>=4 with two blocks is contained in every n-chromatic digraph.
The Minimum Feedback Arc Set Problem is NP-hard for Tournaments (2007)
Charbit, Pierre, Thomasse, Stephan, Yeo, Anders
Answering a question of Bang-Jensen and Thomassen, we prove that the minimum feedback arc set problem is NP-hard for tournaments.
Graphs with Large Girth Not Embeddable in the Sphere (2007)
Charbit, Pierre, Thomasse, Stephan
In 1972, M. Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere $S^d$ in such a way that two vertices joined by an edge have distance more than $\sqrt 3$ (i.e. distance...
Branchwidth of Graphic Matroids (2007)
Branchwidth of Graphs and Matroids were introduced by Robertson and Seymour in their Graph Minor X paper. In 2002, Geelen, Gerards, Robertson and Whittle asked whether the branchwidth of a bridgeless...
Branchwidth of Graphic Matroids (2007)
Branchwidth of Graphs and Matroids were introduced by Robertson and Seymour in their Graph Minor X paper. In 2002, Geelen, Gerards, Robertson and Whittle asked whether the branchwidth of a bridgeless...
Hoàng-Reed conjecture holds for tournaments (2006)
Havet, Frederic, Thomasse, Stephan, Yeo, Anders
Hoàng-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of...
Hoàng-Reed conjecture holds for tournaments (2006)
Havet, Frederic, Thomasse, Stephan, Yeo, Anders
Hoàng-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of...
Density Conditions for Triangles in Multipartite Graphs (2006)
Bondy, Adrian, Shen, Jian, Thomasse, Stephan, Thomassen, Carsten
We consider the problem of finding a large or dense triangle-free subgraph in a given graph $G$. In response to a question of P. Erd\H{o}s, we prove that, if the minimum degree of $G$ is at least...
The Categorical Product of Two 5-Chromatic Digraphs can be 3-Chromatic (2005)
Bessy, Stéphane, Thomasse, Stephan
We provide an example of a 5-chromatic oriented graph $D$ such that the categorical product of $D$ and $TT_5$ is 3-chromatic, where $TT_5$ is the transitive tournament on 5 vertices.
Jørgen Bang-Jensen, Stephan Thomasse
We prove that there is no degree of connectivity which will guarantee that a hypergraph contains two edge-disjoint spanning connected subhypergraphs. We also show that Edmonds' theorem on...
Generalized Pigeonhole Properties of Graphs and Oriented Graphs
Anthony Bonato, Peter Cameron, Dejan Delic, St Ephan, Stephan Thomasse
A relational structure A satis es the P(n; k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic...
Indivisibility and Alpha-Morphisms
A relation R is p-divisible if for any partition of its basis into p + 1 subsets, R is embedded into the union of p of them. We prove that any countable p-divisible relation embeds two copies of...