Zobrazeno 1 - 10
of 22
pro vyhledávání: '"GENIET, COLIN"'
Autor:
Chekan, Vera, Geniet, Colin, Hatzel, Meike, Pilipczuk, Michał, Sokołowski, Marek, Seweryn, Michał T., Witkowski, Marcin
For a group $\Gamma$, a $\Gamma$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $\Gamma$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null i
Externí odkaz:
http://arxiv.org/abs/2408.16344
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
Dallard, Milani\v{c}, and \v{S}torgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when $H$ is any planar co
Externí odkaz:
http://arxiv.org/abs/2302.08182
Autor:
Geniet, Colin, Thomassé, Stéphan
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments $\mathcal T$, first-order model checking is either fixed parameter tractable or $\textrm{AW}[*]$-hard. This dichotomy coin
Externí odkaz:
http://arxiv.org/abs/2207.07683
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
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometry. Thus, through Cayley graphs, it defi
Externí odkaz:
http://arxiv.org/abs/2204.12330
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
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-se
Externí odkaz:
http://arxiv.org/abs/2007.14161
The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $|V(G)|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is
Externí odkaz:
http://arxiv.org/abs/2006.09877