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 Chargé de Recherche CNRS (Junior 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 in charge of the Discrete Mathematics Seminar with András Sebő. Please contact either one of us if you want to give a talk.
- I am a member of the ANR Project GATO (2017-2020).
I am interested in all aspects of graph theory even though most of my research is related to graph coloring. 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.
Publications
Submitted papers
Boxicity, poset dimension, and excluded minors (with V. Wiechert)
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
Least conflict choosability (with Z. Dvořák, R.J. Kang and K. Ozeki)
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 conflict choosability 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:1802.05582
Separation choosability and dense bipartite induced subgraphs (with R.J. Kang and S. Thomassé)
(Partial results from this paper will be 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`?
arXiv:1802.03727
Improper coloring of graphs on surfaces (with I. Choi)
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
Accepted
Exact distance coloring in trees (with N. Bousquet, A. Harutyunyan, and R. de Joannis de Verclos)
Accepted in Combinatorics, Probability and Computing
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
The width of quadrangulations of the projective plane (with M. Stehlík)
Accepted in Journal of Graph Theory
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
2018
Distributed coloring in sparse graphs with fewer colors (with P. Aboulker, M. Bonamy and N. Bousquet)
ACM Symposium on Principles of Distributed Computing (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
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 ejc:v24i2p6
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 ejc:v23i4p4
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 ejc:v23i1p30
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)).
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 ejc:v19i2p40
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
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
Recent talks
- Réunion ANR GATO (Grenoble, France) January 16, 2018 Modular orientations.
- Séminaire Philippe Flajolet (Paris, France) December 7, 2017 Coloration de graphes et autres espaces métriques.
- Réunion ANR STINT (Saint-Maurice-en-Valgaudemar, France) July 5, 2017 Polynomial expansion and sublinear separators.
- Séminaire de Combinatoire et Théorie des Nombres (Lyon, France) March 28, 2017 Bases additives et flots dans les graphes.
- Séminaire de Géométrie Algorithmique et Combinatoire (Paris, France) March 23, 2017 Box representations of embedded graphs.
- Réunion ANR GATO (Palaiseau, France) January 23, 2017 Coloration impropre de graphes plongés sur des surfaces.
- Réunion ANR STINT (Lyon, France) January 19, 2017 Coloration de courbes dans le plan.
Past projects
- PHC Van Gogh "Efficient property testing" (2016-2017)
- ANR STINT (2014-2017)
- Equipe-Action GALOIS du Labex Persyval (2013-2017)
- ANR Heredia (2010-2014)
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)
- Open Problem in Topological Graph Theory (Dan Archdeacon)
Useful links
- FAQ LaTeX (en français)
- 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