Coloring Graphs With No Totally Odd Clique Immersion

Caleb McFarland · 2025

Read Coloring Graphs With No Totally Odd Clique Immersion by Caleb McFarland (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08119.txt.

Introduction

McFarland proved this result in twenty twenty-five in graph theory, the study of networks made of points and links. Colouring a graph means painting its points so linked points differ. An immersion is a pattern hidden inside a graph by routing paths between key points. The paper concerns graphs that avoid an odd version of a complete pattern, where every point links to every other.

McFarland shows such graphs need only a number of colours that grows in step with the pattern size. The proof splits the graph into two parts, one of which is bipartite and one that avoids a smaller immersion. The method is constructive, with an algorithm that finds the split. The result ties colouring bounds to forbidden patterns in a new way.

Catalog record

CREATORCaleb McFarland
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08119

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coloring Graphs With No Totally Odd Clique Immersion Caleb McFarland Abstract We prove that graphs that do not contain a totally odd immersion of K t K_{t} are 𝒪 ⁡ ( t ) \mathcal{O}(t) -colorable. In particular, we show that any graph with no totally odd immersion of K t K_{t} is the union of a bipartite graph and a graph which forbids an immersion of K 𝒪 ⁡ ( t ) K_{\mathcal{O}(t)} . Our results are algorithmic, and we give a fixed-parameter tractable algorithm (in t t ) to find such a decomposition. 1 Introduction It is conjectured that every graph without an odd K_{t} -minor is (t-1) -colorable [ 14 ] . This would be a vast generalization of the famous 4-Color Theorem which to date only has a computer proof [ 2 , 23 ] . Despite a huge amount of recent progress on this problem and on Hadwiger’s Conjecture [ 17 , 21 , 22 , 25 ] , a linear bound remains out of reach. Here, we give the first linear bound for a different notion of graph containment, that is, for graphs with no totally odd K_{t} -immersion. Theorem 1.1 . For every integer t\geq 1 , every graph that does not admit a totally odd immersion of K_{t} is (700{\small,}000t+32{\small,}000{\small,}000) -colorable. A graph G contains a totally odd immersion of K_{t} if there is a way of mapping the vertices of K_{t} into the vertices of G and the edges of K_{t} into edge disjoint trails in G between the corresponding endpoints such that every trail has odd length. All immersions in this paper are weak immersions unless explicitly stated otherwise. We defer the reader to section 2 for formal definitions related to immersions. We derive theorem 1.1 from the following stronger result about graphs with no totally odd immersion. Theorem 1.2 . For every integer t\geq 1 , every graph that does not admit a totally odd immersion of K_{t} is the union of a bipartite graph and a graph which forbids K_{98{\small,}000t+4{\small,}410{\small,}071} as an immersion. We note that for coloring it suffices to consider simple graphs, but the graphs in theorem 1.2 need not be simple. Moreover, our proofs are algorithmic. That is, we obtain the following theorem. Theorem 1.3 . There exists an algorithm that takes as input a multigraph G and an integer t\geq 1 and finds either a totally odd K_{t} -immersion in G , or finds a set of edges F\subseteq E(G) such that G[F] is bipartite and G\setminus F contains no K_{98{\small,}000t+4{\small,}410{\small,}071} -immersion in \mathcal{O}_{t}(|V(G)|^{4}|E(G)|+|E(G)|^{4}) time. These results are motivated by the well-known conjectures of Hajós and Hadwiger on graph coloring. In 1961, Hajós [ 13 ] conjectured that for every integer t\geq 1 , every graph that does not contain a subdivision of K_{t} is (t-1) -colorable. This was disproven by Catlin [ 3 ] for all t\geq 7 . Lescure and Meyniel [ 18 ] , and independently Abu-Khzam and Langston [ 1 ] , proposed a weaker conjecture: Conjecture 1.4 ( [ 18 , 1 ] ) . For every integer t\geq 1 , every graph that does not immerse K_{t} is (t-1) -colorable. 1.4 is known for t\leq 7 due to work of Lescure and Meyniel [ 18 ] and DeVos, Kawarabayashi, Mohar, and Okamura [ 8 ] . 1.4 is also known up to a constant factor, as first shown by DeVos, Dvořák, Fox, McDonald, Mohar, Bojan, and Scheide [ 7 ] , who proved that graphs with no K_{t} -immersion are 200t -colorable. The best known asymptotic bound is that of Gauthier, Le, and Wollan [ 10 ] given below. Theorem 1.5 ( [ 10 , Theorem 1.6] ) . For every integer t\geq 1 , every graph that does not immerse K_{t} is \lceil 3.54t+3\rceil -colorable. 1.4 has obvious similarities with the famous Hadwiger’s Conjecture: for every integer t\geq 1 , every graph that does not contain a K_{t} -minor is (t-1) -colorable. It is still open whether graphs with no K_{t} -minor are \mathcal{O}(t) -colorable. There has been a long line of work improving the asymptotic bounds for Hadwiger’s Conjecture [ 17 , 21 , 22 , 25 ] . The best bound currently is that of Delcourt and Postle [ 6 ] , who prove that graphs with no K_{t} -minor are \mathcal{O}(t\log\log t) -colorable. For t=3 , both Hadwiger’s Conjecture and 1.4 are equivalent to the statement that trees are 2-colorable. There have been different attempts to strengthen both conjectures to give a more precise classification of this case. For Hadwiger’s Conjecture, Gerards and Seymour [ 14 ] proposed the following odd-minor variant. Conjecture 1.6 ( [ 14 ] ) . For every integer t\geq 1 , every graph that does not contain K_{t} as an odd-minor is (t-1) -colorable. A graph is an odd-minor of another if it can be formed from a subgraph via contracting edge cuts. Odd-minors are important because they preserve the parity of cycles. Churchley [ 5 ] conjectured the following for immersions. Conjecture 1.7 ( [ 5 ] ) . For every integer t\geq 1 , every graph that does not admit a totally odd immersion of K_{t} is (t-1) -colorable. In both of the above conjectures, the t=3 case now correctly identifies 2-colorable graphs as those with no odd cycles. The conjectures also say something about dense graphs, as graphs forbidding an odd-minor or totally odd immersion need not be sparse, unlike graphs which forbid a minor [ 17 , 25 ] or immersion [ 7 ] . 1.7 is known for t=4 via a stronger result of Zang [ 27 ] and independently Thomassen [ 26 ] which replaces “totally odd immersion” with “totally odd subdivision”. Jiménez, Quiroz, and Caro [ 15 ] proved 1.7 for line graphs of multigraphs where every edge has the same multiplicity. Steiner [ 24 ] answered 1.6 up to constant factor by showing that the question is equivalent to Hadwiger’s Conjecture up to a factor of 2. In particular they show that in a graph with no odd K_{t} -minor, there exist disjoint bipartite induced subgraphs which can be identified to form a graph with no K_{t} -minor. This implies that if K_{t} -minor free graphs are f(t) -colorable, then odd K_{t} -minor free graphs are 2f(t) -colorable. Our main result is in some ways analogous to Steiner’s result for odd-minors, but our techniques are unrelated. The previous best bound on the chromatic number of graphs without a totally odd K_{t} -immersion is the bound given by Kawarabayashi [ 16 ] , which states that graphs with no totally odd K_{t} subdivision are 79t^{2}/4 -colorable. We provide the first linear bound on the chromatic number of graphs without a totally odd K_{t} -immersion, answering 1.7 up to a constant factor. Graphs which forbid an immersion not only have linear chromatic number, they also have linear degeneracy. A graph is k -degenerate if every subgraph has minimum degree at most k . The degeneracy of K_{t} -immersion free graphs was first shown by DeVos et. al. [ 7 ] , with the best bound being the following due to Gauthier, Le, and Wollan

Read the complete text