Skip to main content
20 votes

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,403
14 votes

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

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

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
8 votes

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,276
6 votes

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,276
4 votes

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

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 Every graph G ...
a3nm's user avatar
  • 9,677

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