Proving a chromatic number upper bound for a graph with a planar subgraph

Question

I have the following problem:

Let $G$ be a graph such that for any partition of its vertices into two sets, the induced subgraph on either of the sets is going to be planar. Prove that $\chi(G) \leq 11$

I cannot use the four-color theorem for this problem, so I suppose I need to use some conditions for planarity like the Kuratowski's theorem, but I'm not sure how.

Answer 1

We may assume that $G$ is not planar. Let $W$ be a minimul subset of the vertex set $V=V(G)$ such that the induced subgraph $G[W]$ is not planar, and choose a vertex $w\in W$. Then $G[V\setminus W]$ and $G[W\setminus\{w\}]$ are planar graphs. By the five color theorem, then, $$\chi(G)\le\chi(G[V\setminus W])+\chi(G[W\setminus\{w\}])+\chi(G[\{w\}])\le5+5+1=11.$$

Answer 2

Are you allowed to use the 5-colors theorem ? it is a standard 'easy' proof done in first graph theory courses usually. Note that if you were allowed to use the 4-ColorTheorem, the argument below would yield $9$ as an upper bound.

If $G$ is planar, we are done by $5$-CT, $\chi(G)\leq 5$. so assume $G$ is not planar.

Note that a partition of the vertices of $G$ into two sets is equivalent to $2$-coloring the vertices. Take a red/blue $2$-coloring of the vertices of $G$. Without loss of generality, assume that $G[Red]$ is planar.

Now start recoloring the blue vertices red, one at a time. Because $G$ is not planar, we know that at one point, $G[Red]$ will not be planar anymore. At this point $G[red]$ is apex (because you can remove one vertex and make it planar), and by the problem statement, $G[blue]$ is planar.

By the $5$-CT, there is a proper coloring $G[red]$ with 6 shades of red, and a proper coloring of $G[blue]$ with 5 shades of blue. This yields a proper coloring of $G$ with 11 colors. (Note that any edge from $G$ not appearing in $G[red]$ nor $G[blue]$ has one red end-point and one blue end-point, so this is a proper coloring of $G$). Hence $\chi(G)\leq 11$.