F. Botler

activity

20152025

most citedSeparating the edges of a graph by a linear number of paths

9 citations · 33 across the 19 of their papers we have counts for

collaborators

Showing math.COShow all

22 papers · 1 filter

math.CO2025

On Modular Edge Colourings of Graphs

Gaétan Berthe, Marthe Bonamy, Fábio Botler +5

Given a graph $G$ and an integer $k \geq 2$ , let $χ_{k}^{'} (G)$ denote the minimum number of colours required to colour the edges of $G$ such that, in each colour class, the subgraph ind…

math.CO2025

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree

Fábio Botler, Cristina G. Fernandes, Carla N. Lintzmayer +4

An immersion of a graph $H$ in a graph $G$ is a minimal subgraph $I$ of $G$ for which there is an injection $i : V (H) \to V (I)$ and a set of edge-disjoint paths $\{P_e:…

math.CO2024

Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs

F. Botler, Y. S. Couto, C. G. Fernandes +4

Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5} n - \frac{18}{5}$ edges has a vertex cut that induces a forest, and co…

math.CO2024

Ramsey Goodness of paths and unbalanced graphs

Fábio Botler, Luiz Moreira, João Pedro de Souza

Given graphs $G$ and $H$ , we say that $G$ is $H$ - $g oo d$ if the Ramsey number $R (G, H)$ equals the trivial lower bound $(∣ G ∣ - 1) (χ (H) - 1) + σ (H)$ , where $χ (H)$ denotes the usual ch…

math.CO2024

Separating the edges of a graph by cycles and by subdivisions of $K_{4}$

Fábio Botler, Tássio Naia

A separating system of a graph $G$ is a family $S$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$ , there exists an element i…

math.CO2023

On nonrepetitive colorings of paths and cycles

Fábio Botler, Wanderson Lomenha, João Pedro de Souza

We say that a sequence $a_{1} \dots a_{2 t}$ of integers is repetitive if $a_{i} = a_{i + t}$ for every $i \in {1, \dots, t}$ . A walk in a graph $G$ is a sequence $v_{1} \dots v_{r}$ of vert…

math.CO2023

Independent dominating sets in planar triangulations

Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez

In 1996, Matheson and Tarjan proved that every near planar triangulation on $n$ vertices contains a dominating set of size at most $n /3$ , and conjectured that this upper bound can…

math.CO2023★ 4 cited

Biclique immersions in graphs with independence number 2

Fábio Botler, Andrea Jiménez, Carla N. Lintzmayer +3

The analogue of Hadwiger's conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{χ (G)}$ . For graphs with independence number 2, this is equ…

math.CO2023★ 9 cited

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

Marthe Bonamy, Fábio Botler, François Dross +2

Recently, Letzter proved that any graph of order $n$ contains a collection $P$ of $O (n lo g^{⋆} n)$ paths with the following property: for all distinct edges $e$ and $f$ …

math.CO2022

Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs

Fábio Botler, Phablo F. S. Moura, Tássio Naia

Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate th…

math.CO2022

The $mod k$ chromatic index of random graphs

Fábio Botler, Lucas Colucci, Yoshiharu Kohayakawa

The $mod k$ chromatic index of a graph $G$ is the minimum number of colors needed to color the edges of $G$ in a way that the subgraph spanned by the edges of each color has…

math.CO2021

Counting orientations of graphs with no strongly connected tournaments

Fábio Botler, Carlos Hoppen, Guilherme Oliveira Mota

Let $S_{k} (n)$ be the maximum number of orientations of an $n$ -vertex graph $G$ in which no copy of $K_{k}$ is strongly connected. For all integers $n$ , $k \geq 4$ where $n \geq 5$ or $k…

math.CO2020

Decomposition of $(2 k + 1)$ -regular graphs containing special spanning $2 k$ -regular Cayley graphs into paths of length $2 k + 1$

Fábio Botler, Luiz Hoffmann

A $P_{ℓ}$ -decomposition of a graph $G$ is a set of paths with $ℓ$ edges in $G$ that cover the edge set of $G$ . Favaron, Genest, and Kouider (2010) conjectured that every $(2k+1…

math.CO2020★ 1 cited

The mod $k$ chromatic index of graphs is $O (k)$

Fábio Botler, Lucas Colucci, Yoshiharu Kohayakawa

Let $χ_{k}^{'} (G)$ denote the minimum number of colors needed to color the edges of a graph $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent t…

math.CO2020★ 5 cited

Counting graph orientations with no directed triangles

Pedro Araújo, Fábio Botler, Guilherme Oliveira Mota

Alon and Yuster proved that the number of orientations of any $n$ -vertex graph in which every $K_{3}$ is transitively oriented is at most $2^{⌊ n^{2} /4 ⌋}$ for $n \geq 1 0^{4}$ …

math.CO2020

On Tuza's conjecture for triangulations and graphs with small treewidth

Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez

Tuza (1981) conjectured that the size $τ (G)$ of a minimum set of edges that intersects every triangle of a graph $G$ is at most twice the size $ν (G)$ of a maximum set of edge-disjo…

math.CO2019

Towards Gallai's path decomposition conjecture

Fabio Botler, Maycon Sambinelli

A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admi…

math.CO2018

Gallai's path decomposition conjecture for triangle-free planar graphs

Fábio Botler, Andrea Jiménez, Maycon Sambinelli

A path decomposition of a graph $G$ is a collection of edge-disjoint paths of $G$ that covers the edge set of $G$ . Gallai (1968) conjectured that every connected graph on $n$ verti…

math.CO2017★ 5 cited

On Gallai's and Hajós' Conjectures for graphs with treewidth at most 3

Fábio Botler, Maycon Sambinelli, Rafael S. Coelho +1

A path (resp. cycle) decomposition of a graph $G$ is a set of edge-disjoint paths (resp. cycles) of $G$ that covers the edge set of $G$ . Gallai (1966) conjectured that every graph…

math.CO2016

Decomposing 8-regular graphs into paths of length 4

Fábio Botler, Alexandre Talon

A $T$ -decomposition of a graph $G$ is a set of edge-disjoint copies of $T$ in $G$ that cover the edge set of $G$ . Graham and Häggkvist (1989) conjectured that any $2 ℓ$ -regular g…

math.CO2015★ 5 cited

Decomposing highly edge-connected graphs into paths of any given length

Fabio Botler, Guilherme O. Mota, Marcio T. I. Oshiro +1

In 2006, Barát and Thomassen posed the following conjecture: for each tree $T$ , there exists a natural number $k_{T}$ such that, if $G$ is a $k_{T}$ -edge-connected graph and $∣ E (G) ∣$ i…

math.CO2015★ 4 cited

Decompositions of highly connected graphs into paths of length five

Fábio Botler, Guilherme O. Mota, Marcio T. I. Oshiro +1

We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that for every tree $T$ there exists a natural number $k_{T}$ such that, if $G$ is a $k_{T}$ -edg…

On Modular Edge Colourings of Graphs

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree

Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs

Ramsey Goodness of paths and unbalanced graphs

Separating the edges of a graph by cycles and by subdivisions of K4​

On nonrepetitive colorings of paths and cycles

Independent dominating sets in planar triangulations

Biclique immersions in graphs with independence number 2

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

Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs

The modk chromatic index of random graphs

Counting orientations of graphs with no strongly connected tournaments

Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1

The mod k chromatic index of graphs is O(k)

Counting graph orientations with no directed triangles

On Tuza's conjecture for triangulations and graphs with small treewidth

Towards Gallai's path decomposition conjecture

Gallai's path decomposition conjecture for triangle-free planar graphs

On Gallai's and Hajós' Conjectures for graphs with treewidth at most 3

Decomposing 8-regular graphs into paths of length 4

Decomposing highly edge-connected graphs into paths of any given length

Decompositions of highly connected graphs into paths of length five

Separating the edges of a graph by cycles and by subdivisions of $K_{4}$

The $mod k$ chromatic index of random graphs

Decomposition of $(2 k + 1)$ -regular graphs containing special spanning $2 k$ -regular Cayley graphs into paths of length $2 k + 1$

The mod $k$ chromatic index of graphs is $O (k)$