Pierre Charbit

Pierre Charbit

Auto-generated profile, based on publicly available information

Pierre Charbit

Université Paris Cité CNRS IRIF F-75013 Paris France

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
17 June 2020 in Algorithmica
Verified
Journal Article
Closed access
PDF file
ÉBÉdouard Bonnet
Édouard Bonnet
NBNicolas Bousquet
Nicolas Bousquet
PCPierre Charbit
Pierre Charbit
STStéphan Thomassé
Stéphan Thomassé
RWRémi Watrigant
Rémi Watrigant


17 October 2020 in HAL
Verified
Preprint
Open access
PDF file
PCPierre Charbit
Pierre Charbit
GHGeňa Hahn
Geňa Hahn
MKMarcin Kamiński
Marcin Kamiński
Manuel LafondManuel Lafond
Manuel Lafond
NLNicolas Lichiardopol
Nicolas Lichiardopol
H Ge Ňa Hahn
Ge Ňa Hahn
The edge clique cover number ecc(G) of a graph G is size of the smallest collection of complete sub-graphs whose union covers all edges of G. Chen, Jacobson, Kézdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw-free, then ecc(G) is bounded above by its order (denoted n). Recently, Javadi and Hajebi verified this conjecture for claw-free graphs with independence number at least three. We study the edge clique cover number of graphs with independence number two, which are necessarily claw-free. We give the first known proof of a linear bound in n for ecc(G) for such graphs, improving upon the bound of O (n 4/3 log 1/3 n) due to Javadi, Maleki and Omoomi. More precisely we prove that ecc(G) is at most the minimum of n + δ (G) and 2n − Ω (n log n), where δ (G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 3 2 n. We also verify the conjecture for some specific subfamilies, for example when the edge packing number with respect to cliques (a lower bound for ecc(G)) equals n, and when G contains no induced subgraph isomorphic to H where H is any fixed graph of order 4.

23 March 2020 in arXiv
Verified
Preprint
Open access
PDF file
MBMarthe Bonamy
Marthe Bonamy
PCPierre Charbit
Pierre Charbit
ODOscar Defrain
Oscar Defrain
GJGwenaël Joret
Gwenaël Joret
ALAurélie Lagoutte
Aurélie Lagoutte
JSJean-Sébastien Sereni
Jean-Sébastien Sereni
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.

17 October 2020 in HAL
Verified
Preprint
Open access
PDF file
PAPierre Aboulker
Pierre Aboulker
PCPierre Charbit
Pierre Charbit
RNReza Naserasr
Reza Naserasr
REReza Extension
Reza Extension
The dichromatic number of a digraph D is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gyárfás-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets F of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of F as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length 3 are 2-colorable. If condition of "triangle-free" is replaced with "K 4-free", then we have an upper bound of 414. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of nice sets that might be of independent interest.

18 October 2022 in arXiv
Verified
Preprint
Open access
PDF file
PCPierre Charbit
Pierre Charbit
MHMichel Habib
Michel Habib
LMLalla Mouatadid
Lalla Mouatadid
RNReza Naserasr
Reza Naserasr
Consider a sequence of LexBFS vertex orderings {\sigma}1, {\sigma}2, . . . where each ordering {\sigma}i is used to break ties for {\sigma}i+1. Since the total number of vertex orderings of a finite graph is finite, this sequence must end in a cycle of vertex orderings. The possible length of this cycle is the main subject of this work. Intuitively, we prove for graphs with a known notion of linearity (e.g., interval graphs with their interval representation on the real line), this cycle cannot be too big, no matter which vertex ordering we start with. More precisely, it was conjectured in [9] that for cocomparability graphs, the size of this cycle is always 2, independent of the starting order. Furthermore [27] asked whether for arbitrary graphs, the size of such a cycle is always bounded by the asteroidal number of the graph. In this work, while we answer this latter question negatively, we provide support for the conjecture on cocomparability graphs by proving it for the subclass of domino-free cocomparability graphs. This subclass contains cographs, proper interval, interval, and cobipartite graphs. We also provide simpler independent proofs for each of these cases which lead to stronger results on this subclasses.