Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Bourneuf, Romain"'
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rz\k{a}\.zewski, Thomass\'e, and Walczak, that for every graph $H$, there is a polynomial $p$ such that for every positive integer $s$, every graph of average degree at least $p(s)$ contains eithe
Externí odkaz:
http://arxiv.org/abs/2311.03341
We show that for any permutation $\pi$ there exists an integer $k_{\pi}$ such that every permutation avoiding $\pi$ as a pattern is a product of at most $k_{\pi}$ separable permutations. In other words, every strict class $\mathcal C$ of permutations
Externí odkaz:
http://arxiv.org/abs/2308.02981
Autor:
Bonnet, Édouard, Bourneuf, Romain, Duron, Julien, Geniet, Colin, Thomassé, Stéphan, Trotignon, Nicolas
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative
Externí odkaz:
http://arxiv.org/abs/2304.04296
Autor:
Bourneuf, Romain, Thomassé, Stéphan
We show that every graph with twin-width $t$ has chromatic number $O(\omega ^{k_t})$ for some integer $k_t$, where $\omega$ denotes the clique number. This extends a quasi-polynomial bound from Pilipczuk and Soko{\l}owski and generalizes a result for
Externí odkaz:
http://arxiv.org/abs/2303.11231
Autor:
Bourneuf, Romain, Folwarczný, Lukáš, Hubáček, Pavel, Rosen, Alon, Schwartzbach, Nikolaj Ignatieff
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erd\H{o}s-Rado sunflower lemma. Implicit v
Externí odkaz:
http://arxiv.org/abs/2209.04827
Publikováno v:
Bourneuf, R, Folwarczný, L, Hubáček, P, Rosen, A & Schwartzbach, N I 2023, PPP-Completeness and Extremal Combinatorics . i 14th Conference on Innovations in Theoretical Computer Science . s. 1-20 . https://doi.org/10.4230/LIPIcs.ITCS.2023.22
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey’s theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit ve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2a53dae3ec07852141eaf0188ba94035