The Stack Overflow podcast is back! Listen to an interview with our new CEO.
19

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 realized by a random graph. The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it'...


18

Being 4-colorable? Certainly MSO, and trivial on planar graphs. It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.


15

The disjoint union of $n$ copies of $K_5$ (or $K_{3,3}$) is a minimal forbidden minor for the graphs of genus $n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are $K_5$ or $K_{3,3}$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus ...


15

It is indeed true that every graph $G$ with no $K_{1,k}$ minor has treewidth at most $k-1$. We prove this below, first a few definitions: Let $tw(G)$ be the treewidth of $G$ and $\omega(G)$ be the maximum size of a clique in $G$. A graph $H$ is a triangulation of $G$ if $G$ is a subgraph of $H$ and $H$ is chordal (i.e has no induced cycles on at least $4$ ...


13

In Sparse obstructions and exact treewidth determination, Lucena states that in the PhD thesis of Sanders, "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."


12

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 Order Ideals (1997) by B. Courcelle, R. Downey, and M. Fellows for a non-computability result (for MSOL-definable graph classes, i.e. classes defined by a ...


12

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$. https://arxiv.org/abs/1410.1016 The proof is shorter than the one for grid minors but it is still not that that easy and builds on several previous tools. ...


10

If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$; you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$. ...


10

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs. Stephan Kreutzer and Ken-ichi Kawarabayashi: The directed grid theorem. arXiv:1411.5681 [cs.DM] EDIT (June 16, 2015): A short version of their paper appears here: Ken-ichi Kawarabayashi, Stephan ...


9

If G is formed from a smaller graph H that is not a clique by adding two vertices x and y, such that x and y are not adjacent to each other but adjacent to all other vertices of G, then $tw(G)=tw(H)+2$. For, in any tree decomposition of $G$, either $x$ and $y$ have disjoint subtrees or they have overlapping subtrees. If they have disjoint subtrees, all the ...


8

The following book covers some material related to the proof of the graph minor theorem (Chapter 12). Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173. The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly ...


8

Johnson et al shown that the planar digraphs are excluding $J_K$ as minor, but they never published this paper, because they were looking to generalize this result. But recently Ken-Ichi Kawarabayashi and Stephan Kreutzer proved "An Excluded Grid Theorem for Digraphs with Forbidden Minors" SODA2014, which generalizes grid theorem on planar directed graphs by ...


7

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 adjacent to the corresponding vertex of the other grid. $G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the ...


7

I found a closely related problem in a paper of Bodaender et. al.. They consider a problem called contraction degeneracy, i.e., the problem to decide for a given Graph $G$ and $k\in \mathbb{N}$ whether all minors of $G$ are $k$-degenerate. Now edge density over all subgraphs of a graph and degeneracy are very similar concepts (if a graph contains a subgraph ...


7

Ok, since there's still nothing here in the way of an answer, let me at least make a couple of simple observations: For graphs of bounded treewidth it should be possible to find a densest minor (or even a minor with specified numbers of edges and vertices) by the usual sort of dynamic program on the tree decomposition, where each state of the dynamic ...


7

For question (2): the subgraph and induced subgraph relations give rise to well quasi orders on some restricted classes of graphs. One of the main references there is an article by G. Ding, Subgraphs and well-quasi-ordering, J. Graph Theory, 16: 489–502, 1992, doi:10.1002/jgt.3190160509. The paper shows that both orderings yield wqos on the class of ...


6

For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are ...


5

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 ``large'' on grids. In applications to PTASes, sub exponential algorithms and kernels on minor-free classes of graphs, "large" means that there exists a constant $c$,...


5

NAUTY can be used as a library to help you build a hashtable for the entire poset of graph minors for small $n$. The key would be the cannonial form given by NAUTY and the value would be a concatenation in sorted order of the cannonical forms of it's direct minors.


5

It is shown that [1] the Mixed Chinese Postman Problem (MCPP) parameterized by pathwidth is $W[1]$-hard, even if all edges and arcs of the input graph $G$ have weight $1$ and is FPT with respect to treedepth. This is the first problem are aware of that has been shown to be $W[1]$-hard with respect to treewidth but FPT with respect to treedepth. Note that the ...


4

The algorithm is described in the proof of Theorem 9. For every proper minor closed class $\mathcal{F}$ and every planar graph $H$ there is a constant $c(\mathcal{F}, H)$ such that if the tree-width of $G\in\mathcal{F}$ is at least $c$, then the answer is positive. Furthermore, the property of containing $H$ as an induced minor is an MSO definable property (...


4

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, even though is too slow to run so we don't actually know what the obstruction set is. So here's another parameterizable family of answers without that flaw (...


4

$\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 the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.


2

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 sketch. Thinking of the torus as $T=S^1\times S^1$, if a non-planar $G$ is embedded without crossing on $T$ then its edges must meet every $S^1\times\{a\}$ and $\{a\...


2

Seems this is a FPT algorithm for a fixed $k$. First of all we can just consider a block which contains $s,t$. If we have a $k\times k$ grid minor which contains $s,t$ then we can find the corresponding chain. As otherwise, as Chekuri et al. shown, the graph has tree width at most $O(k^{1/\delta})$ where $\delta > 0$ is some constant. So we can compute ...


1

counter-examples to above are posted on MathOverflow: https://mathoverflow.net/questions/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1 Any "right" modification of question that still holds true?


1

I think that Robertson and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "almost bounded genus" graphs. The basic building blocks are not planar graphs but graphs of bounded genus (genus depending on the excluded minor). I think that toroidal graphs are not decomposable any further.


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