20 votes
Accepted

Number of 4 cycles

Yes, this is known. For $d = \Omega(n^{1/2})$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $\Omega(d^4)$ total $C_4$s. This is best possible because it's ...
GMB's user avatar
  • 2,393
14 votes
Accepted

Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
Chandra Chekuri's user avatar
12 votes
Accepted

Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second ...
Thomas Klimpel's user avatar
8 votes
Accepted

Hadwiger number under matching contraction

There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid ...
daniello's user avatar
  • 3,266
8 votes
Accepted

Survey on Erdős-Pósa?

I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written: Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. ...
Hermann Gruber's user avatar
6 votes
Accepted

Something-Treewidth Property

For question $1$: any bidimensional parameter has this property on general graphs. A parameter $s(G)$ is bidimensional if the value of $s(G) \geq s(H)$ for every minor $H$ of $G$, and if $s$ is ``...
daniello's user avatar
  • 3,266
4 votes
Accepted

Minor closed properties that are explicitly MSO expressible

I had an answer here involving apex graphs but it fails the definition of not having an explicit obstruction set given in this question: there is a published algorithm for finding the obstruction set, ...
David Eppstein's user avatar
4 votes
Accepted

Minor and subdivision

$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $>3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where ...
David Eppstein's user avatar
3 votes
Accepted

Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

I don't know whether this has been explicitly stated anywhere, but it follows from known results. Every planar graph is a minor of a $O(n)\times O(n)$ grid and such an embedding can be found in linear ...
user67422's user avatar
  • 144
2 votes

Properties of toroidal graph

Regarding (3), yes, if a graph $M$ has two vertex disjoint non-planar induced subgraphs $G$ and $H$, then $G\cup H$ (and hence $M$) is not toroidal. I don't know a reference but here's a proof ...
Bjørn Kjos-Hanssen's user avatar
1 vote

Finding subgraphs with high treewidth and constant degree

In the case of pathwidth, reposting here a comment made to me by email by Benjamin Rossman back in 2020 (see also the comments to the answer https://cstheory.stackexchange.com/a/38943): Every graph G ...
a3nm's user avatar
  • 9,232

Only top scored, non community-wiki answers of a minimum length are eligible