Zobrazeno 1 - 10
of 275
pro vyhledávání: '"Bonamy, Marthe"'
We show that the edges of any planar graph of maximum degree at most $9$ can be partitioned into $4$ linear forests and a matching. Combined with known results, this implies that the edges of any planar graph $G$ of odd maximum degree $\Delta\ge 9$ c
Externí odkaz:
http://arxiv.org/abs/2302.13312
Publikováno v:
Advances in Combinatorics 2023:6, 7pp
Recently, Letzter proved that any graph of order $n$ contains a collection $\mathcal{P}$ of $O(n\log^\star n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $\mathcal{P}$ which contains $e$ but not $f$.
Externí odkaz:
http://arxiv.org/abs/2301.08707
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
We consider Kempe changes on the $k$-colorings of a graph on $n$ vertices. If the graph is $(k-1)$-degenerate, then all its $k$-colorings are equivalent up to Kempe changes. However, the sequence between two $k$-colorings that arises from the proof m
Externí odkaz:
http://arxiv.org/abs/2112.02313
Autor:
Bonamy, Marthe, Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre, Giannopoulos, Panos, Kim, Eun Jung, Rzążewski, Paweł, Sikora, Florian, Thomassé, Stéphan
Publikováno v:
J. ACM 68(2): 9:1-9:38 (2021)
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
http://arxiv.org/abs/2110.15419
Autor:
Bastide, Paul, Bonamy, Marthe, Bonato, Anthony, Charbit, Pierre, Kamali, Shahin, Pierron, Théo, Rabie, Mikaël
The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the gra
Externí odkaz:
http://arxiv.org/abs/2110.10530
In 1968, Gallai conjectured that the edges of any connected graph with $n$ vertices can be partitioned into $\lceil \frac{n}{2} \rceil$ paths. We show that this conjecture is true for every planar graph. More precisely, we show that every connected p
Externí odkaz:
http://arxiv.org/abs/2110.08870
Autor:
Bonamy, Marthe, Bonnet, Édouard, Déprés, Hugues, Esperet, Louis, Geniet, Colin, Hilaire, Claire, Thomassé, Stéphan, Wesolek, Alexandra
Publikováno v:
In Journal of Combinatorial Theory, Series B July 2024 167:215-249
Publikováno v:
In European Journal of Combinatorics June 2024 119
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a $(5-\varepsilon)$-approx
Externí odkaz:
http://arxiv.org/abs/2108.02697