Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Legrand–Duchesne, Clément"'
A seminal result of Koml\'os, S\'ark\"ozy, and Szemer\'edi states that any n-vertex graph G with minimum degree at least (1/2 + {\alpha})n contains every n-vertex tree T of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result
Externí odkaz:
http://arxiv.org/abs/2409.06640
Autor:
Gomes, Guilherme C. M., Legrand-Duchesne, Clément, Mahmoud, Reem, Mouawad, Amer E., Okamoto, Yoshio, Santos, Vinicius F. dos, van der Zanden, Tom C.
We study the problem of reconfiguring one minimum $s$-$t$-separator $A$ into another minimum $s$-$t$-separator $B$ in some $n$-vertex graph $G$ containing two non-adjacent vertices $s$ and $t$. We consider several variants of the problem as we focus
Externí odkaz:
http://arxiv.org/abs/2307.07782
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:
In Journal of Combinatorial Theory, Series B November 2024 169:561-613
Autor:
Deschamps, Quentin, Feghali, Carl, Kardoš, František, Legrand-Duchesne, Clément, Pierron, Théo
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and~$\beta$ whenever the coloring~$\beta$ can be obtained from $\alpha$ by a
Externí odkaz:
http://arxiv.org/abs/2201.07595
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:
C.M. Gomes, Guilherme, Legrand-Duchesne, Clément, Mahmoud, Reem, Mouawad, Amer E., Okamoto, Yoshio, F. dos Santos, Vinicius, van der Zanden, Tom C.
Publikováno v:
In Journal of Computer and System Sciences December 2024 146
Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called
Externí odkaz:
http://arxiv.org/abs/2111.05001
Publikováno v:
In European Journal of Combinatorics June 2024 119
We prove that for any $\varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac32-\varepsilon)t$-colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a conn
Externí odkaz:
http://arxiv.org/abs/2103.10684