# Tag Info

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

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$ ...

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 ...

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

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 ...

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 ...

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

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 ...

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

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$,...

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

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

$\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?

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