Source author record

Pierre Charbit

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

11works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

(P6, triangle)-free digraphs have bounded dichromatic number

The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree T and every integer k, any oriented graph that does not contain an induced copy of T nor a clique of size k has dichromatic number at most some function of k and T.

preprint2022arXiv

Improved pyrotechnics : Closer to the burning graph conjecture

The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$ . The previous best-known result was for graphs with minimum degree $23$ .

preprint2020arXiv

Revisiting a theorem by Folkman on graph colouring

We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.

preprint2016arXiv

$χ$ -bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree $T$ and integer $k$ , if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$ , if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$ , every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results.

preprint2015arXiv

Limits of Structures and the Example of Tree-Semilattices

The notion of left convergent sequences of graphs introduced by Lov\' asz et al. (in relation with homomorphism densities for fixed patterns and Szemerédi's regularity lemma) got increasingly studied over the past $10$ years. Recently, Ne\v set\v ril and Ossona de Mendez introduced a general framework for convergence of sequences of structures. In particular, the authors introduced the notion of $QF$ -convergence, which is a natural generalization of left-convergence. In this paper, we initiate study of $QF$ -convergence for structures with functional symbols by focusing on the particular case of tree semi-lattices. We fully characterize the limit objects and give an application to the study of left convergence of $m$ -partite cographs, a generalization of cographs.

preprint2014arXiv

Graphs with large chromatic number induce $3k$ -cycles

Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large.

preprint2013arXiv

Detecting 2-joins faster

2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes $O(n^3m)$ time where $n$ is the number of vertices of the input graph and $m$ the number of its edges. To detect \emph{non-path} 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time $O(n^4m)$ . Here, we give an $O(n^2m)$ -time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

preprint2013arXiv

On a Generalization of the Ryser-Brualdi-Stein Conjecture

A rainbow matching for (not necessarily distinct) sets F_1,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.

preprint2013arXiv

The graph formulation of the union-closed sets conjecture

In 1979 Frankl conjectured that in a finite non-trivial union-closed collection of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs.

preprint2013arXiv

Vertex elimination orderings for hereditary graph classes

We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vu\vsković. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.

preprint2010arXiv

Linear Time Split Decomposition Revisited

Given a family F of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of F. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition.

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.

Pierre Charbit

Research overview

Is this your work?

11 publications

(P6, triangle)-free digraphs have bounded dichromatic number

Improved pyrotechnics : Closer to the burning graph conjecture

Revisiting a theorem by Folkman on graph colouring

$χ$ -bounded families of oriented graphs

Limits of Structures and the Example of Tree-Semilattices

Graphs with large chromatic number induce $3k$ -cycles

Detecting 2-joins faster

On a Generalization of the Ryser-Brualdi-Stein Conjecture

The graph formulation of the union-closed sets conjecture

Vertex elimination orderings for hereditary graph classes

Linear Time Split Decomposition Revisited

See the researcher in context

Building this map preview

Pierre Charbit

Research overview

Is this your work?

11 publications

(P6, triangle)-free digraphs have bounded dichromatic number

Improved pyrotechnics : Closer to the burning graph conjecture

Revisiting a theorem by Folkman on graph colouring

χχχ-bounded families of oriented graphs

Limits of Structures and the Example of Tree-Semilattices

Graphs with large chromatic number induce 3k3k3k-cycles

Detecting 2-joins faster

On a Generalization of the Ryser-Brualdi-Stein Conjecture

The graph formulation of the union-closed sets conjecture

Vertex elimination orderings for hereditary graph classes

Linear Time Split Decomposition Revisited

See the researcher in context

Building this map preview

$χ$ -bounded families of oriented graphs

Graphs with large chromatic number induce $3k$ -cycles