Julien Duron

activity

20232026

most citedA tamed family of triangle-free graphs with unbounded chromatic number

2 citations · 4 across the 15 of their papers we have counts for

collaborators

Showing math.COShow all

10 papers · 1 filter

math.CO2026

Hereditary 2-WQO Graph Classes Have Bounded Clique-Width

Julien Duron, Nikolas Mählmann, Szymon Toruńczyk

A graph class is $k$ -WQO if its $k$ -labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is $2$ -…

math.CO2026

Decomposing tournaments into comparability graphs

Pierre Aboulker, Logan Crew, Julien Duron +7

In this note, we introduce the \emph{partial order decomposition number} of a digraph $D$ , denoted $p o d (D)$ , defined as the minimum integer $k$ such that $A(D)=A(P_1)\cup\cdots\cup…

math.CO2025

Covering graphs by isometric trees

Paul Bastide, Julien Duron, Jędrzej Hodor +2

A connected subgraph of a graph is isometric if it preserves distances. Recently, graphs admitting a vertex or edge covering by a small number of isometric paths have been studied.…

math.CO2025

Planar induced paths via a decomposition into non-crossing ordered graphs

Julien Duron, Hugo Jacob

In any graph, the maximum size of an induced path is bounded by the maximum size of a path. However, in the general case, one cannot find a converse bound, even up to an arbitrary…

math.CO2024

Long induced paths in sparse graphs and graphs with forbidden patterns

Julien Duron, Louis Esperet, Jean-Florent Raymond

Consider a graph $G$ with a path $P$ of order $n$ . What conditions force $G$ to also have a long induced path? As complete bipartite graphs have long paths but no long induced path…

math.CO2024

Adjacency Labeling Schemes for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +1

A graph class admits an implicit representation if, for every positive integer $n$ , its $n$ -vertex graphs have a $O (lo g n)$ -bit (adjacency) labeling scheme, i.e., their vertices c…

math.CO2023

Tight bounds on adjacency labels for monotone graph classes

Édouard Bonnet, Julien Duron, John Sylvester +2

A class of graphs admits an adjacency labeling scheme of size $b (n)$ , if the vertices in each of its $n$ -vertex graphs can be assigned binary strings (called labels) of length $b(n…

math.CO2023★ 1 cited

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +2

We show that for any natural number $s$ , there is a constant $γ$ and a subgraph-closed class having, for any natural $n$ , at most $γ^{n}$ graphs on $n$ vertices up to isomorphism, bu…

math.CO2023★ 2 cited

A tamed family of triangle-free graphs with unbounded chromatic number

Édouard Bonnet, Romain Bourneuf, Julien Duron +3

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 edg…