8 citations · 20 across the 14 of their papers we have counts for
20 papers
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
Generalising the achromatic number to Zaslavsky's colourings of signed graphs
Julien Bensmail, François Dross, Nacim Oijid +1
The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic th…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
1-planar graphs with minimum degree at least 3 have bounded girth
François Dross
We show that every 1-planar graph with minimum degree at least 4 has girth at most , and every 1-planar graph with minimum degree at least 3 has girth at most .
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
Complexity of planar signed graph homomorphisms to cycles
François Dross, Florent Foucaud, Valia Mitsou +2
We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs…
Graphs with the second and third maximum Wiener index over the 2-vertex connected graphs
Stéphane Bessy, François Dross, Martin Knor +1
Wiener index, defined as the sum of distances between all unordered pairs of vertices, is one of the most popular molecular descriptors. It is well known that among 2-vertex connec…
The structure of graphs with given number of blocks and the maximum Wiener index
Stéphane Bessy, François Dross, Katarína Hriňáková +2
The Wiener index (the distance) of a connected graph is the sum of distances between all pairs of vertices. In this paper, we study the maximum possible value of this invariant amo…
Partitioning sparse graphs into an independent set and a graph with bounded size components
Ilkyoo Choi, François Dross, Pascal Ochem
We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these…
On the unavoidability of oriented trees
François Dross, Frédéric Havet
A digraph is {\it -unavoidable} if it is contained in every tournament of order . We first prove that every arborescence of order with leaves is -unavoidable…
Note on 3-Choosability of Planar Graphs with Maximum Degree 4
François Dross, Borut Lužar, Mária Maceková +1
Deciding whether a planar graph (even of maximum degree ) is -colorable is NP-complete. Determining subclasses of planar graphs being -colorable has a long history, but si…
Vertex partitions of -free planar graphs
François Dross, Pascal Ochem
A graph is -colorable if its vertex set can be partitioned into a graph with maximum degree at most and and a graph with maximum degree at most . We show that…
A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
François Dross, Mickael Montassier, Alexandre Pinlou
We prove that every triangle-free planar graph of order and size has an induced linear forest with at least vertices, and thus at least $\frac{5n + 8}{…
Partitioning sparse graphs into an independent set and a forest of bounded degree
François Dross, Mickael Montassier, Alexandre Pinlou
An -partition of a graph is a partition of the vertices of the graph into two sets and , such that is an independent set and induces a forest…
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
François Dross, Mickael Montassier, Alexandre Pinlou
An -partition of a graph is a vertex-partition into two sets and such that the graph induced by is a forest and the one induced by is a f…
Colouring Diamond-free Graphs
Konrad K. Dabrowski, François Dross, Daniël Paulusma
The Colouring problem is that of deciding, given a graph and an integer , whether admits a (proper) -colouring. For all graphs up to five vertices, we classify th…
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
Konrad K. Dabrowski, Francois Dross, Matthew Johnson +1
A colouring of a graph is a function such that for every . A -regular list assignment of is a function $L…
A lower bound on the order of the largest induced forest in planar graphs with high girth
François Dross, Mickael Montassier, Alexandre Pinlou
We give here new upper bounds on the size of a smallest feedback vertex set in planar graphs with high girth. In particular, we prove that a planar graph with girth and size $m…
Fractional triangle decompositions in graphs with large minimum degree
François Dross
A triangle decomposition of a graph is a partition of its edges into triangles. A fractional triangle decomposition of a graph is an assignment of a non-negative weight to each of…
Large induced forests in planar graphs with girth 4 or 5
François Dross, Mickael Montassier, Alexandre Pinlou
We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth and . In particular we prove that a triangle-free planar graph of ord…