L. Picasarri-Arrieta

activity

20212026

collaborators

29 papers

cs.DS2026

The directed temporal exploration problem

Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang +1

We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of $O (n^{2})$ suffices to guarantee the existence of a temporal exploration on always-unilate…

math.CO2026

Acyclic Dichromatic Number of Tournaments: these are the Champions

Pierre Aboulker, Pierre Charbit, Samuel Coulomb +2

The acyclic dichromatic number of an oriented graph is the minimum size of a vertex-partition such that the digraphs induced by any single part are acyclic, and the oriented bipart…

math.CO2026

Coloring digraphs with $Δ - b$ colors

Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta

The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possib…

math.CO2026

On the list version of a conjecture of Erdős and Neumann-Lara

Ararat Harutyunyan, Lucas Picasarri-Arrieta, Gil Puig i Surroca

The dichromatic number of a digraph $D$ , denoted by $χ (D)$ , is the smallest number of colours required to colour the vertices of $D$ such that each colour class induces an acyc…

math.CO2026

Increasing arc-connectivity by bounded- and fixed-size inversions

Florian Hörsch, Lucas Picasarri-Arrieta

For a digraph $D$ and some $X \subseteq V (D)$ , the inversion of $X$ is the operation of flipping all arcs both of whose endvertices are in $X$ . We initiate the study of establishin…

math.CO2025

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs

Thilo Hartel, Lucas Picasarri-Arrieta, Dieter Rautenbach

Let $G$ be a $K_{4}$ -free graph of order $n$ and let $k$ be an integer with $0 \leq k \leq n$ . We show the existence of positive constants $η$ and $ν$ such that $G$ has at most $(4-η)^…

math.CO2025

Acyclic dichromatic number of oriented graphs

Jørgen Bang-Jensen, Lucas Picasarri-Arrieta, Anders Yeo

The dichromatic number $χ (D)$ of a digraph $D = (V, A)$ is the minimum number of sets in a partition $V_{1}, \dots, V_{k}$ of $V$ into $k$ subsets so that the induced subdigraph $D[V…

math.CO2025

On cuts of small chromatic number in sparse graphs

Guillaume Aubian, Marthe Bonamy, Romain Bourneuf +2

For a given integer $k$ , let $ℓ_{k}$ denote the supremum $ℓ$ such that every sufficiently large graph $G$ with average degree less than $2 ℓ$ admits a separator $X \subseteq…

math.CO2025

Generalized DP-colorings of digraphs

Lucas Picasarri-Arrieta, Michael Stiebitz

In this paper we consider the following three coloring concepts for digraphs. First of all, the generalized coloring concept, in which the same colored vertices of a digraph induce…

cs.CC2025

The Complexity of Finding and Counting Subtournaments

Simon Döring, Sarah Houdaigoui, Lucas Picasarri-Arrieta +1

We study the complexity of counting and finding small tournament patterns inside large tournaments. Given a fixed tournament $T$ of order $k$ , we write ${\#}\text{IndSub}_{\text{To…

math.CO2025

Chromatic discrepancy of locally $s$ -colourable graphs

Timothée Corsini, Lucas Picasarri-Arrieta, Théo Pierron +2

The chromatic discrepancy of a graph $G$ , denoted $ϕ (G)$ , is the least over all proper colourings $σ$ of $G$ of the greatest difference between the number of colours $∣ σ (V (H)) ∣$ sp…

math.CO2025

Backbone colouring of chordal graphs

Júlio Araújo, Nicolas Nisse, Lucas Picasarri-Arrieta

A proper $k$ -colouring of a graph $G = (V, E)$ is a function $c : V (G) \to {1, \dots, k}$ such that $c (u) \neq = c (v)$ for every edge $uv \in E (G)$ . The chromatic number $χ (G)$ is the mini…

math.CO2025

$(Δ - 1)$ -dicolouring of digraphs

Ararat Harutyunyan, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta +1

In 1977, Borodin and Kostochka conjectured that every graph with maximum degree $Δ \geq 9$ is $(Δ - 1)$ -colourable, unless it contains a clique of size $Δ$ . In 1999, Reed confirmed th…

math.CO2025

Edge-colouring and orientations: applications to degree- and $χ$ -boundedness

Arnab Char, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta

We prove a new generalisation of Ramsey's theorem by showing that every $2$ -edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph who…

math.CO2024

Blow-ups and extensions of trees in tournaments

Pierre Aboulker, Frédéric Havet, William Lochet +3

A class of acyclic digraphs $C$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D \in C$ is contained in all tournaments of order…

math.CO2024

An analogue of Reed's conjecture for digraphs

Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta

Reed in 1998 conjectured that every graph $G$ satisfies $χ (G) \leq ⌈ \frac{Δ ( G ) + 1 + ω ( G )}{2} ⌉$ . As a partial result, he proved the existence of $ε > 0$ for which…

math.CO2024

Brooks-type colourings of digraphs in linear time

Daniel Gonçalves, Lucas Picasarri-Arrieta, Amadeus Reinald

Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lovász showed that su…

math.CO2024

The 3-dicritical semi-complete digraphs

Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta

A digraph is $3$ -dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that…

math.CO2024

Complexity results on the decomposition of a digraph into directed linear forests and out-stars

Florian Hörsch, Lucas Picasarri-Arrieta

We consider two decomposition problems in directed graphs. We say that a digraph is $k$ -bounded for some $k \in Z_{\geq 1}$ if each of its connected components contains at…

math.CO2024

Subdivisions in dicritical digraphs with large order or digirth

Lucas Picasarri-Arrieta, Clément Rambaud

Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of…

math.CO2023

Minimum number of arcs in $k$ -critical digraphs with order at most $2 k - 1$

Lucas Picasarri-Arrieta, Michael Stiebitz

The dichromatic number $χ (D)$ of a digraph $D$ is the least integer $k$ for which $D$ has a coloring with $k$ colors such that there is no monochromatic directed cycle in $D$ .…

cs.DM2023

Constrained Flows in Networks

Stéphane Bessy, Jørgen Bang-Jensen, Lucas Picasarri-Arrieta

The support of a flow $x$ in a network is the subdigraph induced by the arcs $uv$ for which $x (uv) > 0$ . We discuss a number of results on flows in networks where we put certain rest…

math.CO2023

Dichromatic number of chordal graphs

Stéphane Bessy, Frédéric Havet, Lucas Picasarri-Arrieta

The dichromatic number of a digraph is the minimum integer $k$ such that it admits a $k$ -dicolouring, i.e. a partition of its vertices into $k$ acyclic subdigraphs. We say that a d…

math.CO2023

Redicolouring digraphs: directed treewidth and cycle-degeneracy

Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau

Given a digraph $D = (V, A)$ on $n$ vertices and a vertex $v \in V$ , the cycle-degree of $v$ is the minimum size of a set $S \subseteq V (D) ∖ {v}$ intersecting every directed…

The directed temporal exploration problem

Acyclic Dichromatic Number of Tournaments: these are the Champions

Coloring digraphs with Δ−b colors

On the list version of a conjecture of Erdős and Neumann-Lara

Increasing arc-connectivity by bounded- and fixed-size inversions

On the number of maximal independent sets and maximal induced bipartite subgraphs in K4​-free graphs

Acyclic dichromatic number of oriented graphs

On cuts of small chromatic number in sparse graphs

Generalized DP-colorings of digraphs

The Complexity of Finding and Counting Subtournaments

Chromatic discrepancy of locally s-colourable graphs

Backbone colouring of chordal graphs

(Δ−1)-dicolouring of digraphs

Edge-colouring and orientations: applications to degree- and χ-boundedness

Blow-ups and extensions of trees in tournaments

An analogue of Reed's conjecture for digraphs

Brooks-type colourings of digraphs in linear time

The 3-dicritical semi-complete digraphs

Complexity results on the decomposition of a digraph into directed linear forests and out-stars

Subdivisions in dicritical digraphs with large order or digirth

Minimum number of arcs in k-critical digraphs with order at most 2k−1

Constrained Flows in Networks

Dichromatic number of chordal graphs

Redicolouring digraphs: directed treewidth and cycle-degeneracy

Coloring digraphs with $Δ - b$ colors

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs

Chromatic discrepancy of locally $s$ -colourable graphs

$(Δ - 1)$ -dicolouring of digraphs

Edge-colouring and orientations: applications to degree- and $χ$ -boundedness

Minimum number of arcs in $k$ -critical digraphs with order at most $2 k - 1$