Zobrazeno 1 - 10
of 381
pro vyhledávání: '"THOMASSÉ, STÉPHAN"'
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph created using Zykov's construction. We give a structural characterizat
Externí odkaz:
http://arxiv.org/abs/2410.06917
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular after Erdos and Selfridge's first result on their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist,
Externí odkaz:
http://arxiv.org/abs/2407.06777
Autor:
Bonnet, Édouard, Feghali, Carl, Nguyen, Tung, Scott, Alex, Seymour, Paul, Thomassé, Stéphan, Trotignon, Nicolas
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible.
Comment: 13 pages
Comment: 13 pages
Externí odkaz:
http://arxiv.org/abs/2402.06338
Autor:
Cautrès, Maxime, Claudet, Nathan, Mhalla, Mehdi, Perdrix, Simon, Savin, Valentin, Thomassé, Stéphan
Publikováno v:
ICALP 2024
We study the notion of $k$-stabilizer universal quantum state, that is, an $n$-qubit quantum state, such that it is possible to induce any stabilizer state on any $k$ qubits, by using only local operations and classical communications. These states g
Externí odkaz:
http://arxiv.org/abs/2402.06260
Autor:
Charbit, Pierre, Thomassé, Stéphan
The results of this note were stated in the first author PhD manuscript in 2006 but never published. The writing of a proof given there was slightly careless and the proof itself scattered across the document, the goal of this note is to give a short
Externí odkaz:
http://arxiv.org/abs/2401.15130
Autor:
Fomin, Fedor V., Le, Tien-Nam, Lokshtanov, Daniel, Saurabh, Saket, Thomasse, Stephan, Zehavi, Meirav
We re-visit the complexity of kernelization for the $d$-Hitting Set problem. This is a classic problem in Parameterized Complexity, which encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex
Externí odkaz:
http://arxiv.org/abs/2308.05974
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
In a directed graph $D$ on vertex set $v_1,\dots ,v_n$, a \emph{forward arc} is an arc $v_iv_j$ where $i
Externí odkaz:
http://arxiv.org/abs/2304.03567
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