Louis Esperet Tel : +33 (0) 4 76 57 45 79 |
I obtained my Ph.D. in Computer Science from the University of Bordeaux in 2008, and my HDR (Habilitation à Diriger les Recherches) from the Université Grenoble Alpes in 2017. In 2008-2009 I was a post-doctoral fellow at Charles University, Prague, Czech Republic. As of October 2009, I work as CNRS researcher in the G-SCOP Laboratory in Grenoble, France. Since April 2018, I am the head of the Combinatorial Optimization group of G-SCOP.
I am interested in all aspects of graph theory and its connections with various fields (mostly in mathematics and computer science). A non-exhaustive list of interests include combinatorial optimisation, probability, extremal combinatorics, (metric) geometry, topology, (distributed) algorithms, property testing and graph limits. I maintain a modest webpage gathering some open problems and questions I studied in the past, with little success. I would be happy to hear about any updates on these problems.
I am in charge of the Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne with Nicolas Bousquet, Jean-Florent Raymond, and Rémi Watrigant, and of the Discrete Mathematics Seminar (currently on hold due to the covid-19 epidemic) with András Sebő. Do not hesitate to contact us if you would like to give a talk.
I am an editor of the journal Discrete Mathematics & Theoretical Computer Science since 2015. I strongly support "diamond" open access, and I hope more journals and conference proceedings will follow this publishing model in the future. Please visit the Free Journal Network for a list of journals running according to the Fair Open Access model. Sometimes I find it difficult to avoid submitting papers to commercial publishers, but in any case free versions of all my papers are available on this webpage.
Publications
Submitted papers
Local certification of graphs on surfaces (with B. Lévêque)
A proof labelling scheme for a graph class `cc "C"` is an assignment of certificates to the vertices of any graph in the class `cc "C"`, such that upon reading its certificate and the certificate of its neighbors, every vertex from a graph `G \in cc "C"` accepts the instance, while if `G \notin cc "C"`, for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface `Sigma`, the class of graphs embeddable in `Sigma` has a proof labelling scheme in which each vertex of an `n`-vertex graph receives a certificate of at most `O(log n)` bits. The proof is quite long and intricate and heavily relies on an earlier result for planar graphs. Here we give a very short proof for any surface. The main idea is to encode a rotation system locally, together with a spanning tree supporting the local computation of the genus via Euler's formula.
arXiv:2102.04133
Local boxicity (with L. Lichev)
A box is the cartesian product of real
intervals, which are either bounded or equal to `\mathbb{R}`. A box is said to be
`d`-local if at most `d` of the intervals are bounded.
In this paper, we investigate the recently
introduced local boxicity of a graph `G`, which is the minimum
`d` such that `G` can be
represented as the intersection of `d`-local boxes in some dimension. We prove that
all graphs of maximum degree `\Delta` have local boxicity `O(\Delta)`, while
almost all graphs of maximum degree `\Delta` have local boxicity
`\Omega(\Delta)`, improving known upper and lower bounds. We also give
improved bounds on the local boxicity as a
function of the number of edges or the genus. Finally, we investigate
local boxicity through the lens of chromatic graph theory. We prove that
the family of
graphs of local boxicity at most 2 is `\chi`-bounded, which means that
the chromatic number of the graphs in this class can be bounded by a
function of their clique number. This extends a classical result on graphs of
boxicity at most 2.
arXiv:2012.04569
Sparse universal graphs for planarity (with G. Joret and P. Morin)
We show that for every integer `n\geq 1` there exists a graph `G_n`
with `n^{1 + o(1)}` edges such that every `n`-vertex planar graph is isomorphic to a subgraph of `G_n`. The best previous bound on the number of edges was `O(n^{3//2})`, proved by Babai, Erdős, Chung, Graham, and Spencer in 1982. We then show that for every integer `n>=1` there is a graph `U_n` with `n^{1+o(1)}` vertices and edges that contains induced copies of every `n`-vertex planar graph. This significantly reduces the number of edges in a recent construction of the authors with Dujmović, Gavoille, and Micek.
arXiv:2010.05779
Accepted papers
Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces (with M. Bonamy, N. Bousquet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott)
Journal of the European Mathematical Society (2021).
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science.
We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.
arXiv:2012.02435
Clustered 3-colouring graphs of bounded degree (with V. Dujmović, P. Morin, B. Walczak, and D.R. Wood)
Combinatorics, Probability and Computing (2021).
A (not necessarily proper) vertex colouring of a graph has "clustering" `c` if every monochromatic component has at most `c` vertices. We prove that planar graphs with maximum degree `Delta` are 3-colourable with clustering `O(Delta^2)`. The previous best bound was `O(Delta^{37})`. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree `Delta` that exclude a fixed minor are 3-colourable with clustering `O(Delta^5)`. The best previous bound for this result was exponential in `Delta`.
arXiv:2002.11721 doi:10.1017/S0963548321000213
Packing and covering balls in graphs excluding a minor (with N. Bousquet, W. Cames van Batenburg, G. Joret, W. Lochet, C. Muller, and F. Pirot)
Combinatorica (2020).
We prove that for every integer `t >=1` there exists a constant `c_t` such that for every `K_t`-minor-free graph `G`, and every set `S` of balls in `G`, the minimum size of a set of vertices of `G` intersecting all the balls of `S` is at most `c_t` times the maximum number of vertex-disjoint balls in `S`. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.
arXiv:2001.04517 doi:10.1007/s00493-020-4423-3
2021
Isometric universal graphs (with C. Gavoille and C. Groenland)
SIAM Journal on Discrete Mathematics 35(2) (2021), 1224-1237.
We show that for any integer `n>= 1`, there is a graph on `3^{n+O(log^2 n)` vertices that contains isometric copies of all `n`-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest.
arXiv:2103.08570 doi:10.1137/21M1406155
Single-conflict colouring (with Z. Dvořák, R.J. Kang and K. Ozeki)
Journal of Graph Theory 97(1) (2021), 148-160.
Given a multigraph, suppose that each vertex is given a local assignment of `k` colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least `k` for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that conflict choosability of simple graphs embeddable on a surface of Euler genus `g` is `O(g^{1/4} log g)` as `g-> oo`. This is sharp up to the logarithmic factor.
arXiv:1803.10962 doi:10.1002/jgt.22646
Distributed algorithms for fractional coloring (with N. Bousquet and F. Pirot)
28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021)
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It is known that for every real `alpha>1` and integer `Delta`, a fractional coloring of total weight at most `alpha(Delta+1)` can be obtained deterministically in a single round in graphs of maximum degree `Delta`, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colourings with a weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. Moreover, we improve on classical bounds on the chromatic number by considering the fractional chromatic number instead, without significantly increasing the output size and the round complexity of the existing algorithms.
arXiv:2012.01752
Optimal labelling schemes for adjacency, comparability and reachability (with M. Bonamy, C. Groenland, and A. Scott)
53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing `2^{Omega(n^2)}` `n`-vertex graphs as `n -> infty`. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an efficient adjacency labelling scheme with labels of `n/4+o(n)` bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of `n/4+o(n)` bits per vertex. All these results are best possible, up to the lower order term, and solve several open problems in the area.
arXiv:2012.01764 doi:10.1145/3406325.3451102
2020
Adjacency Labelling for Planar Graphs (and Beyond) (with V. Dujmović, C. Gavoille, G. Joret, P. Micek, and P. Morin)
61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an `n`-vertex planar graph `G` is assigned a `(1+o(1)) log_2 n`-bit label and the labels of two vertices `u` and `v` are sufficient to determine if `uv` is an edge of `G`. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every `n`, there exists a graph `U_n` with `n^{1+o(1)}` vertices such that every `n`-vertex planar graph is an induced subgraph of `U_n`. These results generalize to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.
arXiv:2003.04280 doi:10.1109/FOCS46700.2020.00060
Local approximation of the Maximum Cut in regular graphs (with E. Bamas)
Theoretical Computer Science 820 (2020), 45-59 (A preliminary version of this paper appeared in WG 2019)
This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least `1/2` in average. When the graph is `d`-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MAXCUT in regular graphs. We first prove that if `G` is `d`-regular, with `d` even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of `1/d` for `d`-regular graphs with `d` odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio `1/d+\epsilon` (with `\epsilon>0`) can run in a constant number of rounds. We also prove results of a similar flavour for the MAXDICUT problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.
arXiv:1902.04899 doi:10.1016/j.tcs.2020.03.008
Planar graphs have bounded nonrepetitive chromatic number (with V. Dujmović, G. Joret, B. Walczak, and D.R. Wood)
Advances in Combinatorics 2020:5, 11pp.
A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.
arXiv:1904.05269 doi:10.19086/aic.12100
Bipartite complements of circle graphs (with M. Stehlík)
Discrete Mathematics 343(6) (2020), 111834.
Using an algebraic characterization of circle graphs, Bouchet proved in 1999 that if a bipartite graph `G` is the complement of a circle graph, then `G` is a circle graph. We give an elementary proof of this result.
arXiv:1910.08388 doi:10.1016/j.disc.2020.111834
2019
Distributed coloring in sparse graphs with fewer colors (with P. Aboulker, M. Bonamy and N. Bousquet)
Electronic Journal of Combinatorics 26(4) (2019), P4.20. (A preliminary version of this paper appeared in PODC 2018)
This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring n-vertex planar graphs with 7 colors in `O(log n)` rounds. Here, we show how to color planar graphs with 6 colors in polylog`(n)` rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every `n`-vertex planar graph with 4 colors in `o(n)` rounds.
arXiv:1802.05582 doi:10.37236/8395
Separation choosability and dense bipartite induced subgraphs (with R.J. Kang and S. Thomassé)
Combinatorics, Probability and Computing 28(5) (2019), 720-732. (Partial results from this paper were presented at ICGT 2018 under the title On dense bipartite induced subgraphs)
We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree `d` contain a bipartite induced subgraph of minimum degree `Omega(log d)` as `d -> oo`?
Our main conjecture was solved (up to a log log term) in this paper.
arXiv:1802.03727 doi:10.1017/S0963548319000026
Exact distance coloring in trees (with N. Bousquet, A. Harutyunyan, and R. de Joannis de Verclos)
Combinatorics, Probability and Computing 28(2) (2019), 177-186.
For an integer `q>= 2` and an even integer `d`, consider the graph obtained from a large complete `q`-ary tree by connecting with an edge any two vertices at distance exactly `d` in the tree. This graph has clique number `q+1`, and the purpose of this short note is to prove that its chromatic number is `\Theta(d \log q//\log d)`. It was not known that the chromatic number of this graph grows with `d`. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant `C` such that for any odd integer `d`, any planar graph can be colored with at most `C` colors such that any pair of vertices at distance exactly `d` have distinct colors. Finally, we study interval coloring of trees (where vertices at distance at least `d` and at most `cd`, for some real `c>1`, must be assigned distinct colors), giving a sharp upper bound in the case of bounded degree trees.
arXiv:1703.06047 doi:10.1017/S0963548318000378
Improper coloring of graphs on surfaces (with I. Choi)
Journal of Graph Theory 91(1) (2019), 16-34.
A graph `G` is `(d_1,...,d_k)`-colorable if its vertex set can be partitioned into `k` sets `V_1,...,V_k`, such that for each `i in {1,..., k}`, the subgraph of `G` induced by `V_i` has maximum degree at most `d_i`. The Four Color Theorem states that every planar graph is `(0,0,0,0)`-colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is `(2,2,2)`-colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus `g>0` is `(0,0,0,9g-4)`-colorable and `(2,2,9g-4)`-colorable. Moreover, these graphs are also `(0,0,O(sqrt{g}),O(sqrt{g}))`-colorable and `(2,O(sqrt{g}),O(sqrt{g}))`-colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus `g` is `(0, 0, O(g))`-colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are `(0, 0, 0)`-colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus `g` is `(0,O(sqrt{g}))`-colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on `g` are tight up to a constant multiplicative factor.
arXiv:1603.02841 doi:10.1002/jgt.22418
Distributed coloring of graphs with an optimal number of colors (with E. Bamas)
International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on coloring graphs of maximum degree `\Delta` with at most `\Delta+1` colors (or `\Delta` colors when some simple obstructions are forbidden). When `\Delta` is a sufficiently large and `k>=\Delta-k_\Delta+1`, for some integer `k_\Delta~~ \sqrt{\Delta}-2`, we give a distributed algorithm that given a `k`-colorable graph `G` of maximum degree `\Delta`, finds a `k`-coloring of `G` in `\min\{O((\log \Delta)^{1/12}\log n), 2^{O(\log \Delta+\sqrt{\log \log n})}\}` rounds, with high probability. The lower bound `\Delta-k_\Delta+1` is best possible in the sense that for infinitely many values of `\Delta`, we prove that when `\chi(G)\le \Delta -k_\Delta`, finding an optimal coloring of `G` requires `\Omega(n)` rounds. Our proof is a light adaptation of a remarkable result of Molloy and Reed, who proved that for `\Delta` large enough, for any `k>= \Delta-k_\Delta` deciding whether `\chi(G)<= k` is in P, while Embden-Weinert et al. proved that for `k<= \Delta-k_\Delta-1`, the same problem is NP-complete. Note that the sequential and distributed thresholds differ by one.
Our first result covers the case where the chromatic number of the graph ranges between `\Delta-\sqrt{\Delta}` and `\Delta+1`. Our second result covers a larger range, but gives a weaker bound on the number of colors: For any sufficiently large `\Delta`, and `\Omega(\log \Delta)<= d <= \Delta/100`, we prove that every graph of maximum degree `\Delta` and clique number at most `\Delta-d` can be efficiently colored with at most `\Delta-\epsilon d` colors, for some absolute constant `\epsilon >0`, with a randomized algorithm running in `O(\log n/\log \log n)` rounds with high probability.
arXiv:1809.08140
2018
Boxicity, poset dimension, and excluded minors (with V. Wiechert)
Electronic Journal of Combinatorics 25(4) (2018), #P4.51.
In this short note, we relate the boxicity of graphs (and the dimension of posets) with their generalized coloring parameters. In particular, together with known estimates, our results imply that any graph with no `K_t`-minor can be represented as the intersection of `O(t^2 log t)` interval graphs (improving the previous bound of `O(t^4))`, and as the intersection of `15/2 t^2` circular-arc graphs.
arXiv:1804.00850 doi:10.37236/7787
The width of quadrangulations of the projective plane (with M. Stehlík)
Journal of Graph Theory 89(1) (2018), 76-88.
We show that every 4-chromatic graph on `n` vertices, with no two vertex-disjoint odd cycles, has an odd cycle of length at most `1//2+sqrt{2n-7//4}`. Let `G` be a non-bipartite quadrangulation of the projective plane on `n` vertices. Our result immediately implies that `G` has edge-width at most `1//2+sqrt{2n-7//4}`, which is sharp for infinitely many values of `n`. We also show that `G` has face-width (equivalently, contains an odd cycle transversal of cardinality) at most `1//4+sqrt{n-15//16}`, which is a constant away from the optimal; we prove a lower bound of `sqrt{n}`. Finally, we show that `G` has an odd cycle transversal of size at most `sqrt{2 Delta n}` inducing a single edge, where `Delta` is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.
arXiv:1509.07716 doi:10.1002/jgt.22241
Additive bases and flows in graphs (with R. de Joannis de Verclos, T.-N. Le, and S. Thomassé)
SIAM Journal on Discrete Mathematics 32(1) (2018), 534-542. (A preliminary version appeared in EuroComb 2017)
It was conjectured by Jaeger, Linial, Payan, and Tarsi in 1992 that for any prime number `p`, there is a constant `c` such that for
any `n`, the union (with repetition) of the vectors of any family of `c` linear bases of `bbb Z_p^n` forms an additive basis of `bbb Z_p^n` (i.e. any element of `bbb Z_p^n` can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two non-zero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that `p>= 3` is a prime number and `vec G` is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in `bbb Z_p`. Then `vec G` has a `bbb Z_p`-flow in which each arc is assigned a value of its own list.
arXiv:1701.03366 doi:10.1137/17M1113758
Polynomial expansion and sublinear separators (with J.F. Raymond)
European Journal of Combinatorics 69 (2018), 49-53.
Let `cc C` be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed `0< delta <= 1`, every `n`-vertex graph of `cc C` has a balanced separator of order `O(n^{1-delta})`, then any depth-`k` minor (i.e. minor obtained by contracting disjoint subgraphs of radius at most `k`) of a graph in `cc C` has average degree `O((k " polylog " k)^{1//delta})`. This confirms a conjecture of Dvorak and Norin.
arXiv:1705.01438 doi:10.1016/j.ejc.2017.09.003
2017
Coloring Jordan regions and curves (with W. Cames van Batenburg and T. Müller)
SIAM Journal on Discrete Mathematics 31(3) (2017), 1670-1684.
A Jordan region is a subset of the plane that is homeomorphic to a closed disk. Consider a family `cc F` of Jordan regions whose interiors are pairwise disjoint, and such that any two Jordan regions intersect in at most one point. If any point of the plane is contained in at most `k` elements of `cc F` (with `k` sufficiently large), then we show that the elements of `cc F` can be colored with at most `k+1` colors so that intersecting Jordan regions are assigned distinct colors. This is best possible and answers a question raised by Reed and Shepherd in 1996. As a simple corollary, we also obtain a positive answer to a problem of Hliněný (1998) on the chromatic number of contact systems of strings.
We also investigate the chromatic number of families of touching Jordan curves. This can be used to bound the ratio between the maximum number of vertex-disjoint directed cycles in a planar digraph, and its fractional counterpart.
arXiv:1608.08159 doi:10.1137/16M1092726
Flows and bisections in cubic graphs (with G. Mazzuoccolo and M. Tarsi)
Journal of Graph Theory 86(2) (2017), 149-158.
A `k`-weak bisection of a cubic graph `G` is a partition of the vertex-set of `G` into two parts `V_1` and `V_2` of equal size, such that each connected component of the subgraph of `G` induced by `V_i` (`i=1,2`) is a tree of at most `k−2` vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph `G` with a circular nowhere-zero `r`-flow has a `lfloor r rfloor`-weak bisection. In this paper we study problems related to the existence of `k`-weak bisections. We believe that every cubic graph which has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching which do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs which do contain bridges.
arXiv:1504.03500 doi:10.1002/jgt.22118
Small feedback vertex sets in planar digraphs (with L. Lemoine and F. Maffray)
Electronic Journal of Combinatorics 24(2) (2017), #P2.6.
Let `G` be a directed planar graph on `n` vertices, with no directed cycle of length less than `g>= 4`. We prove that `G` contains a set `X` of vertices such that `G-X` has no directed cycle, and `|X|<=frac{5n-5}{9}` if `g=4`, `|X|<= {2n-5}/4` if `g=5`, and `|X|<= {2n-6}/g` if `g>= 6`. This improves recent results of Golowich and Rolnick.
arXiv:1606.04419 doi:10.37236/6252
Box representations of embedded graphs
Discrete & Computational Geometry 57(3) (2017), 590-606.
A `d`-box is the cartesian product of `d` intervals of `bbb R` and a `d`-box representation of a graph `G` is a representation of `G` as the intersection graph of a set of `d`-boxes in `bbb R^d`. It was proved by Thomassen in 1986 that every planar graph has a 3-box representation. In this paper we prove that every graph embedded in a fixed orientable surface, without short non-contractible cycles, has a 5-box representation. This directly implies that there is a function `f`, such that in every graph of genus `g`, a set of at most `f(g)` vertices can be removed so that the resulting graph has a 5-box representation. We show that such a function `f` can be made linear in `g`. Finally, we prove that for any proper minor-closed class `cc F`, there is a constant `c(cc F)` such that every graph of `cc F` without cycles of length less than `c(cc F)` has a 3-box
representation, which is best possible.
arXiv:1512.02381 doi:10.1007/s00454-016-9837-8
Graphs with no induced five-vertex path or antipath (with M. Chudnovsky, L. Lemoine, P. Maceli, F. Maffray, and I. Penev)
Journal of Graph Theory 84(3) (2017), 221-232.
We prove that a graph `G` contains no induced 5-vertex path and no induced complement of a 5-vertex path if and only if `G` is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.
arXiv:1410.0871 doi:10.1002/jgt.22022
Long induced paths in graphs (with L. Lemoine and F. Maffray)
European Journal of Combinatorics 62 (2017), 1-14.
We prove that every 3-connected planar graph on `n` vertices contains an induced path on `Omega(log n)` vertices, which is best possible and improves the best known lower bound by a multiplicative factor of `log log n`. We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on `n` vertices, also contains an induced path on `Omega(sqrt{log n})` vertices. We conjecture that for any `k`, there is a contant `c(k)` such that any `k`-degenerate graph with a path on `n` vertices also contains an induced path on `Omega((log n)^{c(k)})` vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.
arXiv:1602.06836 doi:10.1016/j.ejc.2016.11.011
2016
Coloring non-crossing strings (with D. Gonçalves and A. Labourel)
Electronic Journal of Combinatorics 23(4) (2016), #P4.4. (A preliminary version appeared in EuroComb 2009 under the title Coloring a set of touching strings)
For a family of geometric objects in the plane `cc F={S_1,...,S_n}`, define `chi(cc F)` as the least integer `cc l` such that the elements of `cc F` can be colored with `cc l` colors, in such a way that any two intersecting objects have distinct colors. When `cc F` is a set of pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most `k` pseudo-disks, it can be proven that `chi(cc F)<= 3k//2 + o(k)` since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family `cc F` of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of `cc F` are only allowed to "touch" each other. Such a family is said to be `k`-touching if no point of the plane is contained in more than `k` elements of `cc F`. We give bounds on `chi(cc F)` as a function of `k`, and in particular we show that `k`-touching segments can be colored with `k+5` colors. This partially answers a question of Hliněný (1998) on the chromatic number of contact systems of strings.
arXiv:1511.03827 doi:10.37236/5710
The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem (with G. Mazzuoccolo and M. Tarsi)
Journal of Combinatorics 7(2) (2016), 453-479.
For some time the Petersen graph has been the only known Snark with circular flow number 5 (or more, as long as the assertion of Tutte's 5-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago by Macajová and Raspaud, the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval `(1,4) mod 5`. All these sets are symmetric unions of open integer intervals in the ring `RR//5ZZ`. We use the results to design an arsenal of methods for constructing snarks `S` with circular flow number `phi_{c}(S)>=5`. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete.
arXiv:1501.03774 doi:10.4310/JOC.2016.v7.n2.a12
Restricted frame graphs and a conjecture of Scott (with J. Chalopin, Z. Li, and P. Ossona de Mendez)
Electronic Journal of Combinatorics 23(1) (2016), #P1.30.
Scott proved in 1997 that for any tree `T`, every graph with bounded clique number which does not contain any subdivision of `T` as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if `T` is replaced by any graph `H`. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of Erdos). This shows that Scott's conjecture is false whenever `H` is obtained from a non-planar graph by subdividing every edge at least once.
It remains interesting to decide which graphs `H` satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from `K_4` by subdividing every edge at least once. We also prove that if `G` is a 2-connected multigraph with no vertex intersecting every cycle of `G`, then any graph obtained from `G` by subdividing every edge at least twice is a counterexample to Scott's conjecture.
arXiv:1406.0338 doi:10.37236/4424
Islands in graphs on surfaces (with P. Ochem)
SIAM Journal on Discrete Mathematics 30(1) (2016), 206-219.
An island in a graph is a set `X` of vertices, such that each element of `X` has few neighbors outside `X`. In this paper, we prove several bounds on the size of islands in large graphs embeddable on fixed surfaces. As direct consequences of our results, we obtain that:
(1) Every graph of genus `g` can be colored from lists of size 5, in such a way that each monochromatic component has size `O(g)`. Moreover all but `O(g)` vertices lie in monochromatic components of size at most 3.
(2) Every triangle-free graph of genus `g` can be colored from lists of size 3, in such a way that each monochromatic component has size `O(g)`. Moreover all but `O(g)` vertices lie in monochromatic components of size at most 10.
(3) Every graph of girth at least 6 and genus `g` can be colored from lists of size 2, in such a way that each monochromatic component has size `O(g)`. Moreover all but `O(g)` vertices lie in monochromatic components of size at most 16.
While (2) is optimal up to the size of the components, we conjecture that the size of the lists can be decreased to 4 in (1), and the girth can be decreased to 5 in (3). We also study the complexity of minimizing the size of monochromatic components in 2-colorings of planar graphs.
The two conjectures were solved by Zdeněk Dvořák and Sergey Norin in this paper.
arXiv:1402.2475 doi:10.1137/140957883
Boxicity and topological invariants
European Journal of Combinatorics 51 (2016), 495-499.
The boxicity of a graph `G=(V,E)` is the smallest integer `k` for which there exist `k` interval graphs `G_i=(V,E_i)`, `1 <= i <= k`, such that `E=E_1 nn ... nn E_k`. In the first part of this note, we prove that every graph on `m` edges has boxicity `O(sqrt{m log m})`, which is asymptotically best possible. We use this result to study the connection between the boxicity of graphs and their Colin de Verdière invariant, which share many similarities. Known results concerning the two parameters suggest that for any graph `G`, the boxicity of `G` is at most the Colin de Verdière invariant of `G`, denoted by `mu(G)`. We observe that every graph `G` has boxicity `O(mu(G)^4(log mu(G))^2)`, while there are graphs `G` with boxicity `Omega(mu(G) sqrt{log mu(G)})`. In the second part of this note, we focus on graphs embeddable on a surface of Euler genus `g`. We prove that these graphs have boxicity `O(sqrt{g} log g)`, while some of these graphs have boxicity `Omega(sqrt{g log g})`. This improves the previously best known upper and lower bounds. These results directly imply a nearly optimal bound on the dimension of the adjacency poset of graphs on surfaces.
I realized only recently that the `O(sqrt{m log m})` bound on the boxicity was already known (see Theorem 12 in this paper of Chandran, Francis, and Sivadasan (2010)). The bound on the boxicity of graphs of bounded Euler genus has been recently improved in this paper.
arXiv:1503.05765 doi:10.1016/j.ejc.2015.07.020
2015
Equitable partition of graphs into induced forests (with L. Lemoine and F. Maffray)
Discrete Mathematics 338(8) (2015), 1481-1483.
An equitable partition of a graph `G` is a partition of the vertex-set of `G` such that the sizes of any two parts differ by at most one. We show that every graph with an acyclic coloring with at most `k` colors can be equitably partitioned into `k−1` induced forests. We also prove that for any integers `d>=1` and `k>=3^{d−1}`, any `d`-degenerate graph can be equitably partitioned into `k` induced forests.
Each of these results implies the existence of a constant `c` such that for any `k>=c`, any planar graph has an equitable partition into `k` induced forests. This was conjectured by Wu, Zhang, and Li in 2013.
arXiv:1410.0861 doi:10.1016/j.disc.2015.03.019
On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph (with G. Mazzuoccolo)
Discrete Mathematics 338(8) (2015), 1509-1514.
A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge
precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let `m_t` be the supremum of all reals `alpha <= 1` such that for every cubic bridgeless graph `G`, there exist `t` perfect matchings of `G` covering a fraction of at least `alpha` of the edges of `G`. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that `m_5=1`, and implies that `m_4=14//15` and `m_3=4//5`. In the first part of this paper, we show that `m_4=14//15` implies `m_3=4//5`, and `m_3=4//5` implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any `2<= t <= 4` and for any real `tau` lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) `tau` of the edges of a given cubic bridgeless graph can be covered by `t` perfect matching is an NP-complete problem. This resolves a conjecture of Tang, Zhang, and Zhu.
arXiv:1306.2828 doi:10.1016/j.disc.2015.03.017
2014
On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings (with G. Mazzuoccolo)
Journal of Graph Theory 77(2) (2014), 144-157. (A preliminary version appeared in EuroComb 2013)
The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this paper we prove that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. We also construct an infinite family `cc F` of snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs were known. It turns out that the family `cc F` also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least `4m//3`, and we show that this inequality is strict for graphs of `cc F`. We also construct the first known snark with no cycle cover of length less than `4m//3+2`.
arXiv:1301.6926 doi:10.1002/jgt.21778
Coloring planar graphs with three colors and no large monochromatic components (with G. Joret)
Combinatorics, Probability and Computing 23(4) (2014), 551-570.
We prove the existence of a function `f: NN rarr NN` such that the vertices of every planar graph with maximum degree `Delta` can be 3-colored in such a way that each monochromatic component has at most `f(Delta)` vertices. This is best possible (the number of colors cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by Kleinberg, Motwani, Raghavan, and Venkatasubramanian in 1997. Our result extends to graphs of bounded genus.
This paper extends our main result to any proper minor-closed classes (answering our Question 15).
arXiv:1303.2487 doi:10.1017/S0963548314000170
List-coloring claw-free graphs with small clique number (with A. Gyárfás, and F. Maffray)
Graphs and Combinatorics 30(2) (2014), 365-375.
Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.
pdf doi:10.1007/s00373-012-1272-x
Distance-two coloring of sparse graphs (with Z. Dvorak)
European Journal of Combinatorics 36 (2014), 406-415.
Consider a graph `G=(V,E)` and, for each vertex `v in V`, a subset `Sigma(v)` of neighbors of `v`. A `Sigma`-coloring is a coloring of the elements of `V` so that vertices appearing together in some `Sigma(v)` receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set `Sigma(v)`, denoted by `rho(Sigma)`. In this paper we study graph classes `cc F` for which there is a function `f`, such that for any graph `G in cc F` and any `Sigma`, there is a `Sigma`-coloring using at most `f(rho(Sigma))` colors. It is proved that if such a function exists for a class `cc F`, then `f` can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes.
arXiv:1303.3191 doi:10.1016/j.ejc.2013.09.002
2013
A unified approach to distance-two colouring of graphs on surfaces (with O. Amini and J. van den Heuvel)
Combinatorica 33(3) (2013), 253-296. (A preliminary version appeared in SODA09, under the title A unified approach to distance-two colouring of planar graphs)
In this paper we introduce the notion of `Sigma`-colouring of a graph `G`: For given subsets `Sigma(v)` of neighbours of `v`, for every `v in V(G)`, this is a proper colouring of the vertices of `G` such that, in addition, vertices that appear together in some `Sigma(v)` receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner's and Borodin's Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn's result that the list chromatic index is close to the fractional chromatic index.
Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree `Delta` embeddable in some fixed surface is at most `3 Delta //2` plus a constant.
Note that the latest version does not only extend the result of the conference version to graphs embeddable on any given surface, it also fixes a number of problems in the original proof. So, please, do not look at the conference version.
arXiv:0812.1345 doi:10.1007/s00493-013-2573-2
Fire containment in planar graphs (with J. van den Heuvel, F. Maffray, and F. Sipma)
Journal of Graph Theory 73(3) (2013), 267-279.
In a graph `G`, a fire starts at some vertex. At every time step, firefighters can protect up to `k` vertices, and then the fire spreads to all unprotected neighbours. The `k`-surviving rate `rho_k(G)` of `G` is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random. For a given class of graphs `cc G` we are interested in the minimum value `k` such that `rho_k(G) >= epsilon` for some constant `epsilon >0` and all `G in cc G` (i.e., such that linearly many vertices are expected to be saved in every graph from `cc G`).
In this note, we prove that for planar graphs this minimum value is at most 4, and that it is precisely 2 for triangle-free planar graphs.
Our result on planar graphs was improved by this paper.
arXiv:1102.3016 doi:10.1002/jgt.21673
Boxicity of graphs on surfaces (with G. Joret)
Graphs and Combinatorics 29(3) (2013), 417-427.
The boxicity of a graph `G=(V,E)` is the least integer `k` for which there exist `k` interval graphs `G_i=(V,E_i)`, `1<=i<=k`, such that `E=E_1 nn ... nn E_k`. Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface `Sigma` of genus `g` is at most `5g+3`. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.
arXiv:1107.1953 doi:10.1007/s00373-012-1130-x
Acyclic edge-coloring using entropy compression (with A. Parreau)
European Journal of Combinatorics 34(6) (2013), 1019-1027.
An edge-coloring of a graph `G` is acyclic if it is a proper edge-coloring of `G` and every cycle contains at least three colors. We prove that every graph with maximum degree `Delta` has an acyclic edge-coloring with at most `4 Delta - 4` colors, improving the previous bound of `9.62 (Delta - 1)`. Our bound results from the analysis of a very simple randomised procedure using the so-called entropy compression method. We show that the expected running time of the procedure is `O(mn Delta^2 log Delta)`, where `n` and `m` are the number of vertices and edges of `G`. Such a randomised procedure running in expected polynomial time was only known to exist in the case where at least `16 Delta` colors were available.
Our aim here is to make a pedagogic tutorial on how to use these ideas to analyse a broad range of graph coloring problems. As an application, we also show that every graph with maximum degree `Delta` has a star coloring with `2 sqrt(2) Delta^{3//2} + Delta` colors.
arXiv:1206.1535 doi:10.1016/j.ejc.2013.02.007
A complexity dichotomy for the coloring of sparse graphs (with M. Montassier, P. Ochem, and A. Pinlou)
Journal of Graph Theory 73(1) (2013), 85-102.
Gallucio, Goddyn and Hell proved in 2001 that in any minor-closed class of graphs, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. Let `cc F` be a monotone class of graphs containing all planar graphs, and closed under clique-sum of order at most two. Examples of such class include minor-closed classes containing all planar graphs, and such that all minimal obstructions are 3-connected. We prove that for any `k` and `g`, either every graph of girth at least `g` in `cc F` has a homomorphism to `C_{2k+1}`, or deciding whether a graph of girth `g` in `cc F` has a homomorphism to `C_{2k+1}` is NP-complete.
We also show that the same dichotomy occurs when considering 3-colorability or acyclic 3-colorability of graphs under various notions of density that are related to a question of Havel (1969) and a conjecture of Steinberg (1976) about the 3-colorability of sparse planar graphs.
pdf doi:10.1002/jgt.21659
The chromatic number of {P5,K4}-free graphs (with L. Lemoine, F. Maffray, and G. Morel)
Discrete Mathematics 313(6) (2013), 743-754.
Gyárfás conjectured that for any tree `T`, every `T`-free graph `G` with maximum clique size `omega(G)` is `f_T(omega(G))`-colorable, for some function `f_T` that depends only on `T` and `omega(G)`. Moreover, he proved the conjecture when `T` is the path `P_k` on `k` vertices. In the case of `P_5`, the best values or bounds known so far are `f_{P_5}(2)=3` and `f_{P_5}(q)<= 3^{q-1}`. We prove here that `f_{P_5}(3)=5`.
pdf doi:10.1016/j.disc.2012.12.019
2012
Locally identifying coloring of graphs (with S. Gravier, M. Montassier, P. Ochem, and A. Parreau)
Electronic Journal of Combinatorics 19(2) (2012), #P40. (A preliminary version appeared in FCC 2010)
We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring `c` of a graph `G` is said to be locally identifying, if for any adjacent vertices `u` and `v` with distinct closed neighborhood, the sets of colors that appear in the closed neighborhood of `u` and `v` are distinct. Let `chi_{lid}(G)` be the minimum number of colors used in a locally identifying vertex-coloring of `G`. In this paper, we give several bounds on `chi_{lid}` for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether `chi_{lid}(G)=3` for a subcubic bipartite graph `G` with large girth is an NP-complete problem.
arXiv:1010.5624 doi:10.37236/2417
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs (with F. Kardos and D. Král')
European Journal of Combinatorics 33(5) (2012), 767-798. (A preliminary version appeared in EuroComb 2009)
Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear bound in the general case.
(superseded by the next paper in the list)
arXiv:1002.4739 doi:10.1016/j.ejc.2011.09.027
2011
Exponentially many perfect matchings in cubic graphs (with F. Kardos, A. King, D. Král', and S. Norine)
Advances in Mathematics 227 (2011), 1646-1664.
We show that every cubic bridgeless graph `G` has at least `2^{|V(G)|//3656}` perfect matchings. This confirms an old conjecture of Lovász and Plummer.
Note that the arXiv version of the paper uses a different definition of a burl from the journal version of the paper and a different proof of Lemma 18 is given. This simplifies the exposition of our arguments throughout the whole paper.
arXiv:1012.2878 doi:10.1016/j.aim.2011.03.015
2010
Dynamic list coloring of bipartite graphs
Discrete Applied Mathematics 158(17) (2010), 1963-1965.
A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of `G`, denoted by `chi_2(G)`, is called the dynamic chromatic number of `G`. The least integer `k`, such that if every vertex of `G` is assigned a list of `k` colors, then `G` has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of `G`, denoted `ch(G)` (resp. the dynamic choice number, denoted `ch_2(G)`). It was recently conjectured by S. Akbari et al. that for any graph `G`, `ch_2(G)=max(ch(G),chi_2(G))`. In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph `G` with `ch(G)=chi_2(G)=3` and `ch_2(G)=4`. Then, for any integer `k>= 5`, we construct a bipartite graph `G_k` such that `ch(G_k)=chi_2(G_k)=3` and `ch_2(G) >= k`.
I only realised recently that the question I asked at the end of the paper (characterizing graphs `G` with `ch_2^{**}(G)=2`) was already solved by Bondy and Murty in their 1976 textbook Graph Theory with Applications: it can be deduced from the proof of their Lemma 6.1.1 that graphs `G` with `ch_2^{**}(G)=2` are precisely graphs with no connected component isomorphic to an odd cycle.
pdf doi:10.1016/j.dam.2010.08.007
Covering line graphs with equivalence relations (with J. Gimbel and A. King)
Discrete Applied Mathematics 158(17) (2010), 1902-1907.
An equivalence graph is a disjoint union of cliques, and the equivalence number `eq(G)` of a graph `G` is the minimum number of equivalence subgraphs needed to cover the edges of `G`. We consider the equivalence number of a line graph, giving improved upper and lower bounds: `1/3 log_2 log_2 chi(G)<eq(L(G))<=2log_2 log_2 chi(G)+2`. This disproves a recent conjecture that `eq(L(G))` is at most three for triangle-free `G`; indeed it can be arbitrarily large.
To bound `eq(L(G))` we bound the closely-related invariant `sigma(G)`, which is the minimum number of orientations of `G` such that for any two edges `e,f` incident to some vertex `v`, both `e` and `f` are oriented out of `v` in some orientation. When `G` is triangle-free, `sigma(G)=eq(L(G))`. We prove that even when `G` is triangle-free, it is NP-complete to decide whether or not `sigma(G)≤3`.
arXiv:1006.3692 doi:10.1016/j.dam.2010.08.012
An improved linear bound on the number of perfect matchings in cubic graphs (with D. Král', P. Skoda, and R. Skrekovski)
European Journal of Combinatorics 31 (2010), 1316-1334.
We show that every cubic bridgeless graph with `n` vertices has at least `3n//4-10` perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.
arXiv:0901.3894 doi:10.1016/j.ejc.2009.11.008
Acyclic t-improper colourings of graphs with bounded maximum degree (with L. Addario-Berry, R.J. Kang, C.J.H. McDiarmid, and A. Pinlou)
Discrete Mathematics 310(2) (2010), 223-229. (A preliminary version appeared in BCC 2007)
For graphs of bounded maximum degree, we consider acyclic `t`-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic and each colour class induces a graph with maximum degree at most `t`.
We consider the supremum, over all graphs of maximum degree at most `d`, of the acyclic `t`-improper chromatic number and provide `t`-improper analogues of results by Alon, McDiarmid and Reed (1991, RSA 2(3), 277-288) and Fertin, Raspaud and Reed (2004, JGT 47(3), 163-182).
pdf doi:10.1016/j.disc.2008.09.009
A functional programming approach for an energy planning problem (with J. Darlay, Y. Kieffer, G. Naves and V. Weber)
EURO 2010 (24th European conference on operational research).
This paper presents a simple yet efficient heuristic for a large-scale energy management problem. The problem is to schedule the maintenance operations of nuclear power plants and to plan the energy production on a 5-year horizon under uncertainties. It was the subject of the 2010 ROADEF/EURO challenge proposed by the French energy provider EDF. We propose a combinatorial heuristic based on a decomposition of the problem. It allowed us to end up in third position in the challenge.
EURO 2010 website ROADEF/EURO Challenge 2010
2009
Adapted list colouring of planar graphs (with M. Montassier, and X. Zhu)
Journal of Graph Theory 62(2) (2009), 127-138.
Given an edge-colouring `F` of a graph `G`, a vertex colouring of `G` is adapted to `F` if no colour appears at the same time on an edge and on its two endpoints. If for some integer `k`, a graph `G` is such that given any list assignment `L` to the vertices of `G`, with `|L(v)| >= k` for all `v`, and any edge-colouring `F` of `G`, `G` admits a colouring `c` adapted to `F` where `c(v) in L(v)` for all `v`, then `G` is said to be adaptably `k`-choosable. In this note, we prove that `K_5`-minor-free graphs are adaptably 4-choosable, which implies that planar graphs are adaptably 4-colourable and answers a question of Hell and Zhu. We also prove that triangle-free planar graphs are adaptably 3-choosable and give negative results on planar graphs without 4-cycle, planar graphs without 5-cycle, and planar graphs without triangles at distance `t`, for any `t>= 0`.
Note that this paper greatly simplifies some of our proofs and answers some of the questions we raised.
pdf doi:10.1002/jgt.20391
Game colouring of the square of graphs (with X. Zhu)
Discrete Mathematics 309(13) (2009), 4514-4521.
This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if `G` is a forest of maximum degree `Delta>=9`, then `chi_{g}(G^2) <= col_{g}(G^2) <= Delta+3`, and there are forests `G` with `col_{g}(G^2) = Delta +3`. It is also proved that for an outerplanar graph `G` of maximum degree `Delta`, `chi_{g}(G^2) <= col_{g}(G^2) <= 2 Delta + 14`, and for a planar graph `G` of maximum degree `Delta`, `chi_{g}(G^2) <= col_{g}(G^2) <= 23 Delta + 75`.
Some of our results were improved by this paper
pdf doi:10.1016/j.disc.2009.02.014
Boxicity of graphs with bounded degree
European Journal of Combinatorics 30(5) (2009), 1277-1280.
The boxicity of a graph `G=(V,E)` is the smallest `k` for which there exist `k` interval graphs `G_i=(V,E_i)`, `1 <= i <= k`, such that `E=E_1 nn ... nn E_k`. Graphs with boxicity at most `d` are exactly the intersection graphs of (axis-parallel) boxes in `RR^d`. In this note, we prove that graphs with maximum degree `Delta` have boxicity at most `Delta^2+2`, which improves the previous bound of `2 Delta^2` obtained by Chandran et al (J. Combin. Theory Ser. B 98 (2008) 443-445).
My bound of `Delta^2+2` was improved to `O(Delta (log Delta)^2)` by this paper.
pdf doi:10.1016/j.ejc.2008.10.003
On circle graphs with girth at least five (with P. Ochem)
Discrete Mathematics 309(8) (2009), 2217-2222. (A preliminary version appeared in EuroComb 2007)
Circle graphs with girth at least five are known to be 2-degenerate (Ageev, 1999). In this paper, we prove that circle graphs with girth at least `g\ge 5` and minimum degree at least two contain a chain of `g-4` vertices of degree two, which implies Ageev's result in the case `g=5`. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least
`g\ge 5` as well as a precise estimate of their maximum average degree.
pdf doi:10.1016/j.disc.2008.04.054
2008
On induced-universal graphs for the class of bounded-degree graphs (with A. Labourel, and P. Ochem)
Information Processing Letters 108(5) (2008), 255-260.
For a family `cc F` of graphs, a graph `U` is said to be `cc F`-induced-universal if every graph of `cc F` is an induced subgraph of `U`. We give a construction for an induced-universal graph for the family of graphs on `n` vertices with degree at most `k`. For `k` even, our induced-universal graph has `O(n^{k//2})` vertices and for `k` odd it has `O(n^{|~k//2~|-1//k} log^{2+2//k}n)` vertices. This construction improves a result of Butler by a multiplicative constant factor for even case and by almost a multiplicative `n^{1//k}` factor for odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result
of Butler.
pdf doi:10.1016/j.ipl.2008.04.020
Linear choosability of graphs (with M. Montassier, and A. Raspaud)
Discrete Mathematics 308(17) (2008), 3938-3950. (A preliminary version appeared in EuroComb 2005)
A proper vertex coloring of a graph `G` is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph `G` is linearly `L`-list colorable if for a given list assignment `L={L(v): v\in V(G)}`, there exists a linear coloring `c` of `G` such that `c(v) in L(v)` for all `v in V(G)`. If `G` is linearly `L`-list colorable for any list assignment with `|L(v)|>= k` for all `v in V(G)`, then `G` is said to be linearly `k`-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.
Our conjecture stating that subcubic graphs distinct from `K_{3,3}` are linearly 4-choosable was proved in this paper.
pdf doi:10.1016/j.disc.2007.07.112
2007
Oriented coloring of 2-outerplanar graphs (with P. Ochem)
Information Processing Letters 101(5) (2007), 215-219.
A graph `G` is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph `H` is defined as the minimum order of an oriented graph `H'` such that `H` has a homomorphism to `H'`. In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament `QR_{67}`, which implies that their (strong) oriented chromatic number is at most 67.
The result on the oriented chromatic number of 2-outerplanar graphs was improved in this paper.
pdf doi:10.1016/j.ipl.2006.09.007
2006
Acyclic improper choosability of graphs (with A. Pinlou)
CS 2006 (6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications).
We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically `(3,1)^{**}`-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically `(2,5)^{**}`-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability
and acyclic improper choosability of planar graphs are equivalent notions.
pdf doi:10.1016/j.endm.2007.01.037
Manuscripts that will not be published
Surfaces have (asymptotic) dimension 2 (with M. Bonamy, N. Bousquet, C. Groenland, F. Pirot, and A. Scott)
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each monochromatic component has small weak diameter.
In this paper, we prove that for any `p`, the class of graphs excluding `K_{3,p}` as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with monochromatic components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal.
Parts of our results in this paper are included in the more complete follow-up paper.
arXiv:2007.03582
Coloring graphs with no induced subdivision of `K_4^+` (with N. Trotignon)
Let `K_4^+` be the 5-vertex graph obtained from `K_4`, the complete graph on four vertices, by subdividing one edge precisely once (i.e. by replacing one edge by a path on three vertices). We prove that if the chromatic number of some graph `G` is much larger than its clique number, then `G` contains a subdivision of `K_4^+` as an induced subgraph.
arXiv:1901.04170
Frugal Colouring of Graphs (with O. Amini and J. van den Heuvel)
LaBRI, Université Bordeaux 1, Research Report RR-1428-07, May 2007.
A `k`-frugal colouring of a graph `G` is a proper colouring of the vertices of `G` such that no colour appears more than `k` times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and `L(p,q)`-labelling. We also study frugal edge-colourings of multigraphs.
arXiv:0705.0422
(d,1)-total labelling of sparse graphs (with M. Montassier, and A. Raspaud)
LaBRI, Université Bordeaux 1, Research Report RR-1391-06, March 2006.
The `(d,1)`-total number `lambda_{d}^{T}(G)` of a graph `G` is the width of the smallest range of integers that suffices to label the vertices and the edges of `G` so that no two adjacent vertices have the same color, no two incident edges have the same color and the distance between the color of a vertex and the color of any incident edge is at least `d`. This notion was introduced by Havet and Yu in 2002. In this paper, we study the `(d,1)`-total number of sparse graphs and prove that for any `0 < epsilon < 1//2`, and any positive integer `d`, there exists a constant `C_{d,epsilon}` such that for any `epsilon Delta`-sparse graph `G` with maximum degree `Delta`, we have `lambda_{d}^{T}(G)<= Delta + C_{d,epsilon}`.
pdf
Coauthors
Pierre Aboulker, Louigi Addario-Berry, Omid Amini, Etienne Bamas, Marthe Bonamy, Nicolas Bousquet, Wouter Cames van Batenburg, Jérémie Chalopin, Ilkyoo Choi, Maria Chudnovsky, Julien Darlay, Vida Dujmović, Zdenek Dvořák, Cyril Gavoille, John Gimbel, Daniel Gonçalves, Sylvain Gravier, Carla Groenland, András Gyárfás, Ararat Harutyunyan, Jan van den Heuvel, Rémi de Joannis de Verclos, Gwenaël Joret, Ross J. Kang, Frantisek Kardos, Dan Kral', Yann Kieffer, Andrew D. King, Arnaud Labourel, Tien-Nam Le, Laetitia Lemoine, Benjamin Lévêque, Zhentao Li, Lyuben Lichev, Chun-Hung Liu, William Lochet, Peter Maceli, Frédéric Maffray, Giuseppe Mazzuoccolo, Colin J.H. McDiarmid, Piotr Micek, Mickaël Montassier, Grégory Morel, Pat Morin, Carole Muller, Tobias Müller, Guyslain Naves, Sergey Norin, Pascal Ochem, Patrice Ossona de Mendez, Kenta Ozeki, Aline Parreau, Irena Penev, Alexandre Pinlou, François Pirot, André Raspaud, Jean-Florent Raymond, Alex Scott, Félix Sipma, Petr Skoda, Riste Skrekovski, Matej Stehlík, Michael Tarsi, Stéphan Thomassé, Nicolas Trotignon, Bartosz Walczak, Valentin Weber, Veit Wiechert, David R. Wood, Xuding Zhu.
Recent or upcoming talks
- CanaDAM 2021 (Canada/online) May 25, 2021, Non-repetitive coloring. (video)
- Computer Science Seminar (Krakow, Poland/online) May 5, 2021, Universal graphs and labelling schemes.
- Geometry and Analysis on Groups Research Seminar (Vienna, Austria/online) March 9, 2021, Asymptotic dimension of graphs.
- Workshop on Entropy Compression and Related Methods (online) March 8, 2021, Entropy compression for coloring problems.
- Combinatorics Seminar (Warwick, UK/online) March 5, 2021, Asymptotic dimension of graphs.
- Iowa State University Discrete Math Seminar (Ames, USA/online) December 10, 2020, Universal graphs for classes of dense graphs.
- GT Graphes & Optimisation (Bordeaux/online) December 4, 2020, Universal graphs for classes of dense graphs. (video)
- Georgia Tech Graph Theory seminar (Atlanta, USA/online) November 10, 2020, Universal graphs. (video)
- Workshop on Graph Theory & Combinatorics in Thuringia (Thuringia, Germany/online) July 31, 2020, Asymptotic dimension of graphs.
Grants
- Equipe-Action ToFu (Topologie effective et Calcul) du Labex Persyval (2020-2023)
- ANR GrR (2019-2023)
- ANR GATO (2017-2021)
- PHC Van Gogh "Efficient property testing" (2016-2017)
- ANR STINT (2014-2017)
- Equipe-Action GALOIS du Labex Persyval (2013-2017)
- ANR Heredia (2010-2014)
Students and postdoctoral researchers
Postdoctoral researchers
- Wouter Cames van Batenburg (2021)
- François Pirot (2019-2020)
- Andrey Kupavskii (2016, joint supervision with A. Sebo)
- Giuseppe Mazzuoccolo (2012-2013, joint supervision with A. Sebo)
Students
- Felix Klingelhöfer (Ph.D. joint supervision with M. Mühlenthaler and A. Newman)
- Luc Libralesso (Ph.D. 2020, joint supervision with V. Jost and T. Honegger) - Anytime tree search algorithms for combinatorial optimization
- Ugo Giocanti (M.Sc. 2020, joint supervision with M. Stehlík) - Some properties of generalized Kneser graphs
- Sébastien Julliot (M.Sc. 2019) - Distributed algorithms in Unit Disk Graphs
- Etienne Bamas (M.Sc. 2018) - Local algorithms for maximum cut
- Rémi de Joannis de Verclos (M.Sc 2014, Ph.D. 2018, joint supervision with J.S. Sereni) - Order types and property testing
- Laetitia Lemoine (M.Sc. 2012, Ph.D. uncompleted, joint supervision with F. Maffray) - Induced paths and forests in graphs
- Félix Sipma (M.Sc. 2010, joint supervision with F. Maffray) - Firefighters in planar graphs
Internships
- Lyuben Lichev (2020) - Local boxicity
- Julien du Crest (2017) - Clustered coloring in cubic graphs
- Xavier Poulot-Cazajous (2016) - On a conjecture of Archdeacon
Trivia
My Erdős-Bacon number is 6, since my Erdős number is 2 (via John Gimbel, or via András Gyárfás) and my Bacon number is 4. When I was in high school, I played in Edouard et Agrippine, by René de Obaldia, with Vincent Message. One year later, Vincent Message played in Art, by Yasmina Reza, with Emmanuel Leconte. Emmanuel Leconte was in The Sisterhood of the Traveling Pants 2 with Blythe Danner. Blythe Danner was in the cast of Beyond All Boudaries, together with Kevin Bacon. Of course the two first links are made using high school plays instead of Hollywood movies, but well...
Links
Journals
Conferences
Problems
- Open Problem Garden
- Problems of Paul Erdős
- Open Problems - Graph Theory and Combinatorics (Douglas West)
Useful links
- A nice tool to find the source of a LaTeX symbol by drawing a rough picture of it.
- LaTeX text fonts and math fonts
- Beamer user guide (pdf)
- Pgf user guide (pdf)
- The current weather on Mars