Coloring Graphs With No Totally Odd Clique Immersion

We prove that graphs that do not contain a totally odd immersion of $K_t$ are $\mathcal{O}(t)$-colorable.

In particular, we show that any graph with no totally odd immersion of $K_t$ is the union of a bipartite graph and a graph which forbids an immersion of $K_{\mathcal{O}(t)}$.

Our results are algorithmic, and we give a fixed-parameter tractable algorithm (in $t$) to find such a decomposition.