Výsledky vyhledávání - "Louis Esperet"

Publikováno v: European Journal of Combinatorics
European Journal of Combinatorics, 2022, 102, pp.103495. ⟨10.1016/j.ejc.2021.103495⟩
European Journal of Combinatorics, Elsevier, 2022, 102, pp.103495. ⟨10.1016/j.ejc.2021.103495⟩

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f1e266f8b6ae842208cab2de16a8a8cd
https://hal.science/hal-03048296

Zobrazit plný text záznamu

Akademický článek

Polynomial bounds for chromatic number II: Excluding a star‐forest.

Autor: Scott, Alex¹ (AUTHOR), Seymour, Paul² (AUTHOR), Spirkl, Sophie³ (AUTHOR) sspirkl@uwaterloo.ca

Publikováno v: Journal of Graph Theory. Oct2022, Vol. 101 Issue 2, p318-322. 5p.

Zobrazit plný text záznamu

Plný text ve formátu HTML

Local certification of graphs on surfaces

Autor: Louis Esperet, Benjamin Lévêque

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e828e9e80c89f9290ffd32adb9255566

Zobrazit plný text záznamu

Distributed Algorithms for Fractional Coloring

Autor: Nicolas Bousquet, François Pirot, Louis Esperet

Publikováno v: Structural Information and Communication Complexity ISBN: 9783030795269
SIROCCO
28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021)
28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), Jun 2021, Wroclaw, Poland. pp.15-30, ⟨10.1007/978-3-030-79527-6_2⟩

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 was proved by Hasemann, H

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c6aec7ee366ededf2b8a8e98134600bd
https://doi.org/10.1007/978-3-030-79527-6_2

Zobrazit plný text záznamu

Distributed Coloring and the Local Structure of Unit-Disk Graphs

Autor: Arnaud de Mesmay, Louis Esperet, Sébastien Julliot

Publikováno v: Algorithms for Sensor Systems ISBN: 9783030892395
ALGOSENSORS
ALGOSENSORS 2021
ALGOSENSORS 2021, Sep 2021, Lisbonne, Portugal. ⟨10.1007/978-3-030-89240-1_5⟩

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba57844b8a6a787fdcde660e68bf48db
https://doi.org/10.1007/978-3-030-89240-1_5

Zobrazit plný text záznamu

Optimal labelling schemes for adjacency, comparability, and reachability

Autor: Alex Scott, Louis Esperet, Carla Groenland, Marthe Bonamy

Publikováno v: 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 2021, Rome, Italy. pp.1109-1117, ⟨10.1145/3406325.3451102⟩
STOC

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing $2^{\Omega(n^2)}$ $n$-vertex graphs as $n\to \infty$. This regime contains many classes of interest, for instance perfect graphs or comparability gr

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c1b95e2ea3dfe9ea9dfb146f913fa168
https://hal.archives-ouvertes.fr/hal-03039884

Zobrazit plný text záznamu

Isometric universal graphs

Autor: Cyril Gavoille, Carla Groenland, Louis Esperet

Publikováno v: SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2021, 35 (2), pp.1224-1237. ⟨10.1137/21M1406155⟩

A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that co

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::65f20a70328fa353be9ff6c564ba67b7

Zobrazit plný text záznamu

Planar graphs have bounded nonrepetitive chromatic number

Autor: David R. Wood, Gwenaël Joret, Vida Dujmović, Bartosz Walczak, Louis Esperet

Publikováno v: Advances in Combinatorics
Advances in Combinatorics, Alliance of Diamond Open Access Journals, 2020, 5, pp.11. ⟨10.19086/aic.12100⟩
Advances in combinatorics

The following seemingly simple question with surprisingly many connections to various problems in computer science and mathematics can be traced back to the beginning of the 20th century to the work of [Axel Thue](https://en.wikipedia.org/wiki/Axel_T

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2488b2e50e556506664e65b22229b420
https://hal.archives-ouvertes.fr/hal-02165018

Zobrazit plný text záznamu

Clustered 3-Colouring Graphs of Bounded Degree

Autor: Louis Esperet, David R. Wood, Bartosz Walczak, Vida Dujmović, Pat Morin

Publikováno v: Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2022, 31 (1), pp.123-135. ⟨10.1017/S0963548321000213⟩

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 previo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3afa0ab49f9e645afb0338961830dbff
http://arxiv.org/abs/2002.11721

Zobrazit plný text záznamu

Improper coloring of graphs on surfaces

Autor: Ilkyoo Choi, Louis Esperet

Publikováno v: Journal of Graph Theory. 91:16-34

A graph $G$ is $(d_1,\ldots,d_k)$-colorable if its vertex set can be partitioned into $k$ sets $V_1,\ldots,V_k$, such that for each $i\in\{1, \ldots, k\}$, the subgraph of $G$ induced by $V_i$ has maximum degree at most $d_i$. The Four Color Theorem

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::3b95b00bcc8800f09dc4ad52f661f025
https://doi.org/10.1002/jgt.22418

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání