Source author record

Nicolas Lichiardopol

Nicolas Lichiardopol appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO

Catalog footprint

What is connected

2works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Disjoint cycles of different lengths in graphs and digraphs

Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $k \geq 1$, every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ has $k$ vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the $k$ cycles are requested to have different lengths congruent to some values modulo some $r$. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have $k$ vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.

preprint2011arXiv

Strong connectivity and directed triangles in oriented graphs. Partial results on a particular case of the Caccetta-Häggkvist conjecture

A particular case of Caccetta-Häggkvist conjecture, says that a digraph of order $n$ with minimum out-degree at least $1/3n$ contains a directed cycle of length at most 3. Recently, Kral, Hladky and Norine proved that a digraph of order $n$ with minimum out-degree at least $0.3465n$ contains a directed cycle of length at most 3 (which currently is the best result). A weaker particular case says that a digraph of order $n$ with minimum semi-degree at least $1/3n$ contains a directed triangle. In a recent paper, by using the result of Kral et al, the author proved that for $β\geq 0.343545$, any digraph $D$ of order $n$ with minimum semi-degree at least $βn$ contains a directed cycle of length at most 3 (which currently is the best result). This means that for a given integer $d\geq 1$, every digraph with minimum semi-degree $d$ and of order $md$ with $m\leq 2.91082$, contains a directed cycle of length at most 3. In particular, every oriented graph with minimum semi-degree $d$ and of order $md$ with $m\leq 2.91082$, contains a directed triangle. In this paper, by using the result of Kral et al, we prove that every oriented graph with minimum semi-degree $d$, of order $md$ with $2.91082< m\leq 3$ and of strong connectivity at most $0.679d$, contains a directed triangle. This will be implied by a more general and more precise result, valid not only for $2.91082< m\leq 3$ but also for larger values of $m$. As application, we improve two existing results. The first result (Authors Broersma and Li), concerns the number of the directed cycles of length 4 of a triangle free oriented graph of order $n$ and of minimum semi-degree at least $\frac{n}{3}$. The second result (Authors Kelly, Kühn and Osthus), concerns the diameter of a triangle free oriented graph of order $n$ and of minimum semi-degree at least $\frac{n}{5}$.