Edge-colored flat graphs

Question

Say that an undirected graph without loops or multiple edges is $n$-colored if its edges are labelled with numbers in $\{ 1, \ldots, n \}$ so that adjacent edges have different labels.

Theorem [Alon-Marshall] For all $n$, there is an $n$-colored graph $G_n$ with at most $5n^4$ vertices such that for every planar $n$-colored graph $G$ there is a color-preserving morphism $G \to G_n$.

Question Is there in the literature an analogous statement for flat graphs?

A graph is flat if it can be embedded into 3-space in such a way that every cycle bounds a disk which is disjoint from the rest of the graph.

Answer 1

As shown in the Alon-Marshall paper you cite, an analogous statement holds for any class of graphs with bounded acyclic chromatic number (Indeed, their result for planar graphs relies only on the fact that every planar graph has acyclic chromatic number at most $5$).

More precisely, Theorem 2.3 in that paper says that for every $k$ and every $n$, there exists a graph $G_n$ on at most $k n^{k-1}$ vertices, whose edges are colored by $1, \dotsc, n$, such that for every graph $H$ on $n$ vertices, with acyclic chromatic number at most $k$, and which is edge-coloured using $1, \dotsc, n$; maps homomorphically into $G_n$.

Thus we would get an analogous result for flat graphs if we can show that the class of flat graphs have acyclic chromatic number at most $k$, for some integer $k \geq 0$. By using arguments of Nešetřil and Ossona de Mendez we can show that indeed some non-specified value $k$ as above exists. The argument goes as follows:

1. The class of flat graphs is equivalent to the class of linklessly embeddable graphs. All such graphs have chromatic number at most $5$ (see https://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29#Special_cases_and_partial_results for details).
2. Nešetřil and Ossona de Mendez (see Theorem 1.1 in their paper) that the acyclic chromatic number of any graph $G$ is bounded from above by $f(r)$, where $r$ is the maximum chromatic number over all minors $H$ of $G$, and $f$ some function.
3. Combining both facts, we get that $k = f(5)$ is such that any flat graph has acyclic chromatic number at most $k$.

I have not checked if the function $f$ in the paper is explicit, but that would give you a concrete value for $k$. You can also avoid this if you happened to get a bound for the acyclic chromatic number of flat graphs, I also have not checked if such bounds exist.

Nešetřil, Jaroslav; Ossona de Mendez, Patrice, Colorings and homomorphism of minor closed classes, Aronov, Boris (ed.) et al., Discrete and computational geometry. The Goodman-Pollack Festschrift. Berlin: Springer (ISBN 3-540-00371-1/hbk). Algorithms Comb. 25, 651-664 (2003). ZBL1071.05526.