By P. Ossona de Mendez

[missing]

We considered Topological minors and Shallow Minors. (Stbility by $*K_p$) Both have bounded expansion for bounded average degree, chromatic number, and are ND for bounded clique number.

Topological minor – paths representing edges are vertex disjoint. Minor – each vertex is represented by sugraph. What if we relax his requirement and allow edges to be only edge disjoint – we get an immersion.

[obr 1]

To avoid previous case we define a shallow immertion, which has bounded number of times the vertex can be traversed by an edge by r.

For $K_t$ we have :

  • Top minor – $\delta(G) \geq ct^2$ [ Komlos-Szemerédi, Bollobás-Thomason]
  • Minor – $rt\sqrt{\log t}$ [ Kostochka, Thomasson ]
  • Shallow immertions – $\delta(v) \geq 11r+t$ [ Dvorák-Yepvenyan ]

What if we grow every vertex to a small compelte graph? We could avoid crossing the vertex many times. Does it change sparsity?

Def: $G*K_p : (v,\alpha) v\in G, \alpha \in K_p; (v,\alpha)(u,\beta) \text{ if } uv$ or $u=v$ and $\alpha \neq \beta$. [obr 2]

Lemma: $\tilde\nabla_r(gK_p) \leq p(p+2r) \tilde\nabla_r(G) + p$ Pf: Let $H \in (GK_p)\tilde\nabla_r$ such that ${||H||\over |H|} = \tilde\nabla_r(G*K_p)$ [obr 3]

  1. No branch contains two twins except if the branch is edge linking them.
  2. Assume we have a subdivision vertex v of a branch corresponding to an edge $e \in H$ which is a twin to a principal vertex of H -> delete e.

We deleted at most $(p-1)|H|$. ${||H_1|| \over |H_1|} \geq {||H|| \over |H|}-(p-1)$

Conflict graph of $H_1$: $V(C)=E(H_1)$.

  • a~b if a,b are not subdivideed and their endpoints are equal to twins. [obr 4]
  • a and b are subdivided and one subdivision vertex of a is a twin of one subdivision vertex of b. [obr 5]

$\Delta(C) \leq \max(p^2-1, 2(p-1)r)$, $\chi(G) \leq \Delta(C) +1 \leq \max(p^2, 2(p-1)r+1)$. We will take a coloring with this number of colors.

$H_2$ is the largest color class. $||H_2|| \geq {||H_1|| \over max(\dots)}$. $H_3 \subseteq G$ vertices of the … (path)?

[obr 6] Q (Shallow immersion, $\leq 2r$ subdivision, $\leq r$ crossings at a vertex) Corollary: $\tilde\nabla_r(G) \leq Q(G) \leq \tilde\nabla_r(G*K_r) \leq 3r^2\tilde\nabla_r(G) +r$

(Stbility by $*K_p$) For shallow immersions: bounded expansion if average degree, chromatic number, W and ND for $\omega$ are less than $\infty$.

degeneracy $deg(G)=\max_{H \subseteq G} \delta(H) = \lfloor mad(G)\rfloor$. Greedy algorithm for coloring – color by the first free color given that vertices are colored according to a linear order. A coloring number is minimum over such linear orders $col(G)=\min_{<} \max_{v\in V(G)} |{u \leq v, u~v \text{ or } u=v}|$ = maximum back degree +1.

Let ch(G) be choosability of G.

$\chi(G) \leq ch(G) \leq col(G)$

Degeneracy is the same as the coloring number: $col(G)=deg(G)+1$

Lemma[Chrobak, Eppstein]: $G$ has an acyclic orientation $\arrow G$ with \Delta^-(\arrow G) \leq k$ if and only if $deg(G) \leq k$.

Lemma[Hakimi]: $\lambda: V(G) \rightarrow \mathbb{N}$, $\exists$ orientation of $G$ such that $d^-(v) \leq \lambda(v)$ $\Rightleftarrow \foreach A\subseteq V(G), ||G[A]|| \leq \sum_{v \in A} \lambda(v)$. Moreover, if $||G||=\sum_{v\in V(G)} \lambda(G)$ then $d^-(V) = \lambda(v)$.

$G, k\in \mathbb{N}, \exists$ unique partition $A,B$ of $V(G)$ such that

  • $G[A]$ is $k$-degenerate
  • $\lambda(G[B]) > k$

which we can get by gradually adding vertices of degree $<k$ to $A$.

We can use the partition A,B, so $\chi(G[A]) \leq k+1$ and $\delta(G[B]) \leq {2||G[B]|| \over |B|} \leq {2||G|| \over |B|}$ and $\chi(G[B]) \leq |B| \leq {2 ||G|| \over k}$ therefore $\chi(G) \leq \chi(G[B]) +\chi(G[A]) \leq 2\sqrt{2||G||}$