6
$\begingroup$

I was wondering if the following result is known (or if there's a nice short proof without treewidth/brenchwidth related theorems): as the title says, suppose you have a graph without a big clique minor but which has a big grid minor; then, show that it either has an induced wall or the line graph of an induced wall as an induced subgraph.

Any input welcome, thanks!

EDIT: Here's a paper I googled randomly that includes all the definitions from above (and also a picture of what a wall graph is - see page 6): http://www.automata.rwth-aachen.de/~grohe/pub/grokawree13.pdf.

$\endgroup$
5
+50
$\begingroup$

The structure of graphs with big tree-width but no big clique minor is partially described by the Flat-wall theorem (Theorem 9.8 of GM XIII). With Ken Kawarabayashi and Robin Thomas, we recently posted a new proof of this result - http://arxiv.org/abs/1207.6927.

I don't know of your proposed theorem having appeared anywhere else, and I don't know of any short proof avoiding the usual graph minor technicalities. Here, though, is an outline of a proof using the standard graph minors tools.

By the Flat-wall Theorem, if there is no $K_t$ minor and the tree-width is sufficiently big, then there exists an induced subgraph H containing an $r'$-wall $W$ such that $H$ has a decomposition up to 3-separations capturing the wall.

This means that there exist pairwise edge disjoint subgraphs $H_0, H_1, \dots, H_s$ such that:

a) $\bigcup_0^s H_i = H$,

b) $|H_i \cap H_0| \le 3$ for $i \ge 1$ and $H_i \cap H_j \subseteq H_0$ for $i, j \ge 1$, $i \neq j$, and

c) $H_i - H_0$ contains at most one vertex of $W$ of $deg_W = 3$.

d) Let $\bar{H}_0$ be the graph obtained from $H_0$ by adding an edge to every pair of non-adjacent vertices $x, y$ for which there exists an index $i$ with $x, y \in H_i \cap H_0$. Then $\bar{H}_0$ is planar and for all $i \ge 1$, there exists a face of $\bar{H}_0$ containing $V(H_i) \cap V(H_0)$.

Consider the subgraph of $H$ induced by the wall $W$. It again has a decomposition satisfying a) - d) above (just take the subgraphs $H_i \cap W$ for $i = 0, \dots, s$.) We first do some analysis on the subgraphs $H_i$ for $i \ge 1$. By picking the wall and decomposition together to minimize the number of vertices in the wall, it is not too hard to show that each $H_i$ can be embedded in the plane using using the rural societies theorem of Robertson and Seymour. The conclusion is that we may assume that the subgraph induced by the wall is in fact planar.

To prove the theorem, one now must only show it for a wall with some edges added in a planar way. This should be possible by first taking every second vertical and every second horizontal path of the wall so that the only edges not contained in the wall should form triangles with two edges incident a vertex of degree 3 in the wall.

$\endgroup$
1
  • $\begingroup$ Thanks for the write-up. I'll check it in a bit (my ideas were similar). Btw, nice new proof for Flat-wall, I got to read your paper last week! $\endgroup$ Oct 18 '13 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.