Zobrazeno 1 - 10
of 261
pro vyhledávání: '"Esperet, Louis"'
Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to
Externí odkaz:
http://arxiv.org/abs/2409.15404
Autor:
Esperet, Louis, Giocanti, Ugo
Publikováno v:
Electronic Journal of Combinatorics 31(2) (2024), P2.41
We study geometric and topological properties of infinite graphs that are quasi-isometric to a planar graph of bounded degree. We prove that every locally finite quasi-transitive graph excluding a minor is quasi-isometric to a planar graph of bounded
Externí odkaz:
http://arxiv.org/abs/2312.08902
Publikováno v:
49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and th
Externí odkaz:
http://arxiv.org/abs/2311.16953
Hadwiger's Conjecture asserts that every $K_h$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic co
Externí odkaz:
http://arxiv.org/abs/2306.06224
Autor:
Esperet, Louis, Giocanti, Ugo
Publikováno v:
Discrete Mathematics 347(4) (2024), 113842
Gromov (2003) constructed finitely generated groups whose Cayley graphs contain all graphs from a given infinite sequence of expander graphs of unbounded girth and bounded diameter-to-girth ratio. These so-called Gromov monster groups provide example
Externí odkaz:
http://arxiv.org/abs/2306.03474
Publikováno v:
Journal of Combinatorial Theory, Series B 169 (2024), 561-613
An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent
Externí odkaz:
http://arxiv.org/abs/2304.01823
Publikováno v:
SIAM Journal on Discrete Mathematics 38(3) (2024), 2181-2193
For any hereditary graph class $F$, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$. As a consequence, we show that, if $F$ admits efficient adjacency labels (o
Externí odkaz:
http://arxiv.org/abs/2206.02872
Autor:
Bonamy, Marthe, Bonnet, Édouard, Déprés, Hugues, Esperet, Louis, Geniet, Colin, Hilaire, Claire, Thomassé, Stéphan, Wesolek, Alexandra
Publikováno v:
Journal of Combinatorial Theory, Series B 167 (2024), 215-249
A graph is $\mathcal{O}_k$-free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) $\mathcal{O}_k$-free graphs have treewidth (even,
Externí odkaz:
http://arxiv.org/abs/2206.00594
Autor:
Esperet, Louis
Let $G$ be a $q$-regular bipartite graph with bipartition $(U,V)$. It was proved by Lu, Wang, and Yan in 2020 that $G$ has a spanning subgraph $H$ such that each vertex of $U$ has degree 1 in $H$, and each vertex of $V$ has degree distinct from 1 in
Externí odkaz:
http://arxiv.org/abs/2205.14904
Autor:
Esperet, Louis, Wood, David R.
Publikováno v:
European Journal of Combinatorics 121 (2024), 103847
Recent results show that several important graph classes can be embedded as subgraphs of strong products of simpler graphs classes (paths, small cliques, or graphs of bounded treewidth). This paper develops general techniques to bound the chromatic n
Externí odkaz:
http://arxiv.org/abs/2205.04953