Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Chudnovsky, Maria"'
Autor:
Chudnovsky, Maria, Seymour, Paul
Publikováno v:
Journal of Combinatorial Theory, Series B. 161:331-381
A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {\em even} if it has an even number of vertices. An {\em even-hole-free} graph is a graph with no even holes. A vertex of a graph is {\em bisimp
Let $G$ be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph $G$ with no balanced skew-partition is either complete or has an even pair.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5871ec556762e44549420c3f803dd6f8
http://arxiv.org/abs/2305.00532
http://arxiv.org/abs/2305.00532
We prove that every connected $P_5$-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected $P_5$-free graph $G$ with independence number at least three contains a three-vertex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f9c6b1b91f99d971e928792608b55183
http://arxiv.org/abs/2301.13175
http://arxiv.org/abs/2301.13175
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of $P_6$-free graphs. Thi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94b6b923829cbbe2176d77177dd027a7
Given a graph $H$, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to $H$, if and only if $H$ is a forest.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2a4645498de17889bcdd4164c283d3da
The celebrated Erd\H{o}s-P\'{o}sa Theorem, in one formulation, asserts that for every $c\geq 1$, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of $c$ cycles have bounded treewidth. What can we say about the treewid
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::62a4e09b4358052d938de0e269ef1e53
The family of cycle completable graphs has several cryptomorphic descriptions, the equivalence of which has heretofore been proven by a laborious implication-cycle that detours through a motivating matrix completion problem. We give a concise proof,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b6da320f22e78685f1d6afbf64d0ea1e
Autor:
Abrishami, Tara, Alecu, Bogdan, Chudnovsky, Maria, Hajebi, Sepehr, Spirkl, Sophie, Vušković, Kristina
The tree-independence number tree-$\alpha$, first defined and studied by Dallard, Milani\v{c} and \v{S}torgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::35ab1f0be49013cb0f8912fb23de49b2
We say a class $\mathcal{C}$ of graphs is clean if for every positive integer $t$ there exists a positive integer $w(t)$ such that every graph in $\mathcal{C}$ with treewidth more than $w(t)$ contains an induced subgraph isomorphic to one of the foll
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bdf455996a1a80d62d180271adf05595
http://arxiv.org/abs/2212.02737
http://arxiv.org/abs/2212.02737
Autor:
Chudnovsky, Maria, Nevo, Eran
Publikováno v:
European Journal of Combinatorics. 110:103699
We provide lower and upper bounds on the minimum size of a maximum stable set over graphs of flag spheres, as a function of the dimension of the sphere and the number of vertices. Further, we use stable sets to obtain an improved Lower Bound Theorem