Source author record

Louis Esperet

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Geometry Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

23works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Distributed coloring and the local structure of unit-disk graphs

Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $4ω(G)$ colors, where $ω(G)$ is the clique number of $G$ . This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68ω(G)+1$ colors in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4ω(G)$ , which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximately) $4ω(G)$ colors in the LOCAL model. We provide partial results towards this conjecture using Fourier-analytical tools.

preprint2022arXiv

Local certification of graphs on surfaces

A proof labelling scheme for a graph class $\mathcal{C}$ is an assignment of certificates to the vertices of any graph in the class $\mathcal{C}$ , such that upon reading its certificate and the certificates of its neighbors, every vertex from a graph $G\in \mathcal{C}$ accepts the instance, while if $G\not\in \mathcal{C}$ , for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface $Σ$ , the class of graphs embeddable in $Σ$ 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.

preprint2022arXiv

Planar graphs have bounded nonrepetitive chromatic number

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.

preprint2021arXiv

Local boxicity

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 $Δ$ have local boxicity $O(Δ)$ , while almost all graphs of maximum degree $Δ$ have local boxicity $Ω(Δ)$ , 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 $χ$ -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.

preprint2020arXiv

Bipartite complements of circle graphs

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.

preprint2016arXiv

Coloring non-crossing strings

For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$ , define $χ(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting objects have distinct colors. When $\mathcal{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 $χ(\mathcal{F})\le 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 $\mathcal{F}$ of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of $\mathcal{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 $\mathcal{F}$ . We give bounds on $χ(\mathcal{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.

preprint2016arXiv

Long induced paths in graphs

We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $Ω(\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 $Ω(\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 $Ω((\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.

preprint2016arXiv

Restricted frame graphs and a conjecture of Scott

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 Erdős). 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 contained in every cycle of $G$ , then any graph obtained from $G$ by subdividing every edge at least twice is a counterexample to Scott's conjecture.

preprint2015arXiv

Boxicity and topological invariants

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 \le i \le k$ , such that $E=E_1 \cap \cdots \cap 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 $μ(G)$ . We observe that every graph $G$ has boxicity $O(μ(G)^4(\log μ(G))^2)$ , while there are graphs $G$ with boxicity $Ω(μ(G)\sqrt{\log μ(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 $Ω(\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.

preprint2015arXiv

Equitable partition of graphs into induced forests

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\ge 1$ and $k\ge 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 \ge c$ , any planar graph has an equitable partition into $k$ induced forests. This was conjectured by Wu, Zhang, and Li in 2013.

preprint2015arXiv

Islands in graphs on surfaces

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.

preprint2015arXiv

On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph

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 $α\le 1$ such that for every cubic bridgeless graph $G$ , there exist $t$ perfect matchings of $G$ covering a fraction of at least $α$ 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=\tfrac{14}{15}$ and $m_3=\tfrac45$ . In the first part of this paper, we show that $m_4=\tfrac{14}{15}$ implies $m_3=\tfrac45$ , and $m_3=\tfrac45$ 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\le t \le 4$ and for any real $τ$ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) $τ$ 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.

preprint2015arXiv

The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem

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 Macajova 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)$ modulo $5$ . All these sets are symmetric unions of open integer intervals in the ring $\mathbb{R}/5\mathbb{Z}$ . We use the results to design an arsenal of methods for constructing snarks $S$ with circular flow number $ϕ_c(S)\ge 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.

preprint2014arXiv

Coloring planar graphs with three colors and no large monochromatic components

We prove the existence of a function $f :\mathbb{N} \to \mathbb{N}$ such that the vertices of every planar graph with maximum degree $Δ$ can be 3-colored in such a way that each monochromatic component has at most $f(Δ)$ 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.

preprint2013arXiv

Acyclic edge-coloring using entropy compression

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, also show that every graph with maximum degree Delta has a star coloring with 2 sqrt(2) Delta^{3/2} + Delta colors.

preprint2013arXiv

Distance-two coloring of sparse graphs

Consider a graph $G = (V, E)$ and, for each vertex $v \in V$ , a subset $Σ(v)$ of neighbors of $v$ . A $Σ$ -coloring is a coloring of the elements of $V$ so that vertices appearing together in some $Σ(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 $Σ(v)$ , denoted by $ρ(Σ)$ . In this paper we study graph classes $F$ for which there is a function $f$ , such that for any graph $G \in F$ and any $Σ$ , there is a $Σ$ -coloring using at most $f(ρ(Σ))$ colors. It is proved that if such a function exists for a class $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.

preprint2013arXiv

On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings

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 $\cal 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 $\cal 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 $\tfrac43m$ , and we show that this inequality is strict for graphs of $\cal F$ . We also construct the first known snark with no cycle cover of length less than $\tfrac43m+2$ .

preprint2012arXiv

A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

In this paper we introduce the notion of $Σ$ -colouring of a graph $G$ : For given subsets $Σ(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 $Σ(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 $Δ$ embeddable in some fixed surface is at most $\frac32\,Δ$ plus a constant.

preprint2012arXiv

Boxicity of graphs on surfaces

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 \le i \le k$ , such that $E=E_1 \cap ... \cap 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 $Σ$ of genus $g$ is at most $5g+3$ . This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.

preprint2012arXiv

Fire Containment in Planar Graphs

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 $ρ_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 $\cG$ we are interested in the minimum value $k$ such that $ρ_k(G)\geε$ for some constant $ε>0$ and all $G\in\cG$ i.e., such that linearly many vertices are expected to be saved in every graph from $\cG$). 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.

preprint2012arXiv

Locally identifying coloring of graphs

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 $χ_{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 $χ_{lid}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $χ_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem.

preprint2011arXiv

Exponentially many perfect matchings in cubic graphs

We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. This 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.

preprint2009arXiv

An improved linear bound on the number of perfect matchings in cubic graphs

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.

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

Building this map preview

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

Louis Esperet

Research overview

Is this your work?

23 publications

Distributed coloring and the local structure of unit-disk graphs

Local certification of graphs on surfaces

Planar graphs have bounded nonrepetitive chromatic number

Local boxicity

Bipartite complements of circle graphs

Coloring non-crossing strings

Long induced paths in graphs

Restricted frame graphs and a conjecture of Scott

Boxicity and topological invariants

Equitable partition of graphs into induced forests

Islands in graphs on surfaces

On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph

The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem

Coloring planar graphs with three colors and no large monochromatic components

Acyclic edge-coloring using entropy compression

Distance-two coloring of sparse graphs

On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings

A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

Boxicity of graphs on surfaces

Fire Containment in Planar Graphs

Locally identifying coloring of graphs

Exponentially many perfect matchings in cubic graphs

An improved linear bound on the number of perfect matchings in cubic graphs

See the researcher in context

Building this map preview