Coloring Graphs With No Totally Odd Clique Immersion

Abstract

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.