2026-07-22T22:30:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23202 2025-10-02T12:42:52Z ddc:004 open_access

Immersions and Albertson’s Conjecture Fox, Jacob Pach, János Suk, Andrew Immersions crossing numbers chromatic number 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.4(k-1) vertices. As an application, we make some progress on Albertson’s conjecture on crossing numbers of graphs, 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.4(k-1) vertices and k is sufficiently large. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Fox and János Pach and Andrew Suk 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.50 urn:nbn:de:0030-drops-232022 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.50 eng https://creativecommons.org/licenses/by/4.0/legalcode