Zobrazeno 1 - 10
of 639
pro vyhledávání: '"CHUDNOVSKY, MARIA"'
Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X\cap Y=\varnothing$ and there is no edge in $G$ with an end in $X$ and an end in $Y$. We prove that every graph $G$ of sufficiently large treewidth contains two anticomplete sets of v
Externí odkaz:
http://arxiv.org/abs/2411.11842
We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large constellation; that is, a complete bipartite induced minor model such th
Externí odkaz:
http://arxiv.org/abs/2410.16495
Publikováno v:
Discrete Mathematics, Volume 343, Issue 5, 2020
The fork is the tree obtained from the claw $K_{1,3}$ by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs.
Com
Com
Externí odkaz:
http://arxiv.org/abs/2408.15005
We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c>0 such that for every integer n>1 every n-vertex even-hole-free gr
Externí odkaz:
http://arxiv.org/abs/2407.08927
We prove that for every $t\in \mathbb{N}$ there exists $\tau=\tau(t)\in \mathbb{N}$ such that every (theta, prism, $K_{1,t}$)-free graph has tree independence number at most $\tau$ (where we allow "prisms" to have one path of length zero).
Externí odkaz:
http://arxiv.org/abs/2406.13053
Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We con
Externí odkaz:
http://arxiv.org/abs/2406.07799
Autor:
Chudnovsky, Maria, Trotignon, Nicolas
We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependance grow arbit
Externí odkaz:
http://arxiv.org/abs/2405.07471
Autor:
Chudnovsky, Maria, Hatzel, Meike, Korhonen, Tuukka, Trotignon, Nicolas, Wiederrecht, Sebastian
We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contai
Externí odkaz:
http://arxiv.org/abs/2405.01879
A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration.
Externí odkaz:
http://arxiv.org/abs/2405.00265
We prove that for every integer $t\geq 1$ there exists an integer $c_t\geq 1$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\log{n}$. This resolves a conjecture of Sintiari and Trotignon, who als
Externí odkaz:
http://arxiv.org/abs/2402.14211