Zobrazeno 1 - 10
of 59
pro vyhledávání: '"Louis Esperet"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AE,..., Iss Proceedings (2005)
A proper vertex coloring of a non oriented graph $G=(V,E)$ is linear if the graph induced by the vertices of two color classes is a forest of paths. A graph $G$ is $L$-list colorable if for a given list assignment $L=\{L(v): v∈V\}$, there exists a
Externí odkaz:
https://doaj.org/article/9db66e890e4144c29890d336e12b7934
Autor:
Louis Esperet, Lyuben Lichev
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⟩
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
https://hal.science/hal-03048296
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
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⟩
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
https://doi.org/10.1007/978-3-030-79527-6_2
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⟩
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
https://doi.org/10.1007/978-3-030-89240-1_5
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
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
https://hal.archives-ouvertes.fr/hal-03039884
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⟩
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
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
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
https://hal.archives-ouvertes.fr/hal-02165018
Publikováno v:
Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2022, 31 (1), pp.123-135. ⟨10.1017/S0963548321000213⟩
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
http://arxiv.org/abs/2002.11721
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
https://doi.org/10.1002/jgt.22418