Coloring and immersion

Definitions and mathematical statement

Let $G$ be a finite loopless undirected graph; parallel edges may be retained as distinct edges. A proper vertex coloring assigns different colors to adjacent vertices, and $\chi(G)$ is the minimum number of colors required. For an integer $t\ge1$, an immersion of $K_t$ in $G$ consists of distinct vertices $b_1,\ldots,b_t$ and, for each unordered pair $\{i,j\}$, a path $P_{ij}$ from $b_i$ to $b_j$ such that all these paths are pairwise edge-disjoint.

This uses the weak immersion convention: different paths may meet at internal vertices, and a branch vertex $b_i$ may occur internally on another pair's path. A strong immersion would additionally exclude that latter possibility and is a different assertion. The paths may otherwise be taken simple, since cycles can be removed from an individual path.

The conjecture states that every finite graph $G$ contains an immersion of $K_{\chi(G)}$. Equivalently, for every positive integer $t$, a graph with chromatic number at least $t$ should have an immersed complete graph of order $t$. Extra edges and vertices of $G$ can be ignored.

The edge-disjointness requirement distinguishes immersion from a complete minor, whose connected branch sets must be vertex-disjoint. Immersion also differs from a subdivision, which requires the internal vertices of distinct edge paths to be disjoint. The target here is the edge-disjoint path model above, with its branch-vertex convention fixed explicitly so that these related notions cannot be confused.

Short English statement

Must every graph contain a weak immersion of a complete graph whose order equals its chromatic number?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3229 (OPG-550), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Coloring and immersion. Original problem and discussion. http://www.openproblemgarden.org/op/coloring_and_immersion.