Francois Dross | DeepAI

AI Chat

Featured Co-authors

Michał Pilipczuk
62 publications
Daniël Paulusma
59 publications
Marcin Pilipczuk
51 publications
Tomáš Masařík
39 publications
Matthew Alastair Johnson
35 publications
Marthe Bonamy
30 publications
Florent Foucaud
23 publications
O-joung Kwon
19 publications
Karol Węgrzycki
18 publications
Théo Pierron
17 publications
Eric Sopena
17 publications

∙ 01/20/2023

Separating the edges of a graph by a linear number of paths

Recently, Letzter proved that any graph of order n contains a collection...

0 Marthe Bonamy, et al. ∙

∙ 09/19/2022

Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours

In this paper, we study problems of connecting classes of points via non...

0 Francois Dross, et al. ∙

∙ 10/14/2021

On the proper interval completion problem within some chordal subclasses

Given a property (graph class) Π, a graph G, and an integer k, the Π-com...

0 Francois Dross, et al. ∙

∙ 09/28/2021

Generalising the achromatic number to Zaslavsky's colourings of signed graphs

The chromatic number, which refers to the minimum number of colours requ...

0 Julien Bensmail, et al. ∙

∙ 08/02/2020

Tree pivot-minors and linear rank-width

Tree-width and its linear variant path-width play a central role for the...

0 Konrad K. Dabrowski, et al. ∙

∙ 01/15/2020

1-planar graphs with minimum degree at least 3 have bounded girth

We show that every 1-planar graph with minimum degree at least 4 has gir...

0 Francois Dross, et al. ∙

∙ 12/03/2019

Jones' Conjecture in subcubic graphs

We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...

0 Marthe Bonamy, et al. ∙

∙ 07/07/2019

Complexity of planar signed graph homomorphisms to cycles

We study homomorphism problems of signed graphs. A signed graph is an un...

0 Francois Dross, et al. ∙

∙ 05/07/2019

The structure of graphs with given number of blocks and the maximum Wiener index

The Wiener index (the distance) of a connected graph is the sum of dista...

0 Stéphane Bessy, et al. ∙

∙ 05/07/2019

Graphs with the second and third maximum Wiener index over the 2-vertex connected graphs

Wiener index, defined as the sum of distances between all unordered pair...

0 Stéphane Bessy, et al. ∙

∙ 05/06/2019

Partitioning sparse graphs into an independent set and a graph with bounded size components

We study the problem of partitioning the vertex set of a given graph so ...

0 Ilkyoo Choi, et al. ∙

∙ 12/12/2018

On the unavoidability of oriented trees

A digraph is n-unavoidable if it is contained in every tournament of or...

0 Francois Dross, et al. ∙

∙ 11/23/2017

Vertex partitions of (C_3,C_4,C_6)-free planar graphs

A graph is (k_1,k_2)-colorable if its vertex set can be partitioned into...

0 Francois Dross, et al. ∙

∙ 06/22/2015

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

We consider a natural restriction of the List Colouring problem: k-Regul...

0 Konrad K. Dabrowski, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world