Immersions and Albertson's conjecture

2025/10/07 by Fox, Jacob, Pach, Janos, Suk, Andrew · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.05893

Abstract

A graph is said to contain K_k (a clique of size k) as a weak immersion if it has k vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger's conjecture: Every graph of chromatic number k contains K_k as a weak immersion. We prove this conjecture for graphs with at most (1.64-o(1))k vertices. As an application, we make some progress on Albertson's conjecture, according to which every graph G with chromatic number k satisfies cr(G) ≥ cr(K_k). In particular, we show that the conjecture is true for all graphs of chromatic number k, provided that they have at most (1.64-o(1))k vertices.

Citations

• Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
• Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• Forcing clique immersions through chromatic number
• Complete graph immersions and minimum degree
• On topological graphs with at most four crossings per edge
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Towards The Albertson Conjecture

Cited by

• Progress on Albertson's Conjecture
• Coloring Graphs With No Totally Odd Clique Immersion

Related

• Forcing clique immersions through chromatic number
• Complete graph immersions in dense graphs
• Clique immersion in graphs without fixed bipartite graph
• Constructing graphs with no immersion of large complete graphs
• Strengthening strong immersions with Kempe chains