2025/02/14 by Henry Echeverría, Echeverría, Henry, Andrea Jiménez +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2502.10227
For a graph G, let im(G) denote the maximum integer t such that G contains Kt as an immersion. A recent paper of Collins, Heenehan, and McDonald (2023) studied the behaviour of this parameter under graph products, asking how large can im(G∗ H) be in terms of im(G) and im(H), when ∗ is one of the four standard graph products. We consider a similar question for the parameter toi(G) which denotes the maximum integer t such that G contains Kt as a totally odd immersion. As an application, we obtain that no minimum counterexample to the immersion-analogue of the Odd Hadwiger Conjecture can be obtained from the Cartesian, direct (tensor), lexicographic or strong product of graphs.