BOUSQUET , Nicolas

In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It is known that for every real $\alpha>1$ and integer $\Delta$, a fractional coloring of total weight at most...

A very nice result of Bárány and Lehel asserts that every finite subset X or can be covered by X-boxes (i.e. each box has two antipodal points in X). As shown by Gyárfás and Pálvőlgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is...

In this work, we generalize several results on graph recolouring to digraphs. Given two k-dicolourings of a digraph D, 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 maintaining a dicolouring at any step even for k = 2 and for digraphs with maximum degree 5...

In this work, we generalize several results on graph recolouring to digraphs. Given two k-dicolourings of a digraph D, 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 maintaining a dicolouring at any step even for k = 2 and for digraphs with maximum degree 5...

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every...

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every...