Zobrazeno 1 - 10
of 667
pro vyhledávání: '"CHUDNOVSKY, MARIA"'
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph, that satisfies some property definable in C
Externí odkaz:
http://arxiv.org/abs/2412.14836
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