Zobrazeno 1 - 10
of 614
pro vyhledávání: '"Chudnovsky, Maria"'
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
Autor:
Chudnovsky, Maria, Cizek, Michal, Crew, Logan, Mináč, Ján, Nguyen, Tung T., Spirkl, Sophie, Tân, Nguyên Duy
The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, we utilize tools from group theory and ring theory to study this proble
Externí odkaz:
http://arxiv.org/abs/2401.06062
A consistent path system in a graph $G$ is an intersection-closed collection of paths, with exactly one path between any two vertices in $G$. We call $G$ metrizable if every consistent path system in it is the system of geodesic paths defined by assi
Externí odkaz:
http://arxiv.org/abs/2311.09364
A clock is a graph consisting of an induced cycle $C$ and a vertex not in $C$ with at least two non-adjacent neighbours in $C$. We show that every clock-free graph of large treewidth contains a "basic obstruction" of large treewidth as an induced sub
Externí odkaz:
http://arxiv.org/abs/2311.05719
Given an integer $k>4$ and a graph $H$, we prove that, assuming P$\neq$NP, the List-$k$-Coloring Problem restricted to $H$-free graphs can be solved in polynomial time if and only if either every component of $H$ is a path on at most three vertices,
Externí odkaz:
http://arxiv.org/abs/2311.05713