Coloring Graphs With No Totally Odd Clique Immersion

2025/08/11 by McFarland, Caleb
#05C15 #05C83 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2508.08119

Abstract

We prove that graphs that do not contain a totally odd immersion of K_t are 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_O(t). Our results are algorithmic, and we give a fixed-parameter tractable algorithm (in t) to find such a decomposition.

Citations

• Disproof of the Odd Hadwiger Conjecture
• Immersions and Albertson's conjecture
• Totally odd immersions of complete graphs in graph products
• Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
• Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
• Clique immersion in graphs without fixed bipartite graph
• Further Progress towards the List and Odd Versions of Hadwiger's Conjecture
• An even better Density Increment Theorem and its application to Hadwiger's Conjecture
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• Forcing clique immersions through chromatic number
• The Kelmans-Seymour conjecture IV: a proof
• The structure of graphs not admitting a fixed immersion
• Finding topological subgraphs is fixed-parameter tractable
• Graph decomposition with applications to subdivisions and path systems modulo k

Related

• Forcing clique immersions through chromatic number
• Constructing graphs with no immersion of large complete graphs
• Immersions and Albertson's conjecture
• Clique immersion in graphs without fixed bipartite graph
• A new upper bound on the chromatic number of graphs with no odd K_t minor