Lescure–Meyniel conjecture for strong immersions

About 11 years old · traced to

Let GG be a graph, let χ(G)\chi(G) denote its chromatic number, and let Kχ(G)K_{\chi(G)} be the complete graph on χ(G)\chi(G) vertices. A strong immersion of a graph HH in GG consists of an injection from V(H)V(H) to V(G)V(G) and pairwise edge-disjoint paths representing the edges of HH, whose internal vertices avoid the image of the injection. Lescure–Meyniel conjecture. Every graph GG contains a strong immersion of Kχ(G)K_{\chi(G)}. This is the strong-immersion analogue of Hadwiger's conjecture. It implies the Abu-Khzam–Langston conjecture for weak immersions, and both conjectures remain open in general; the statement is known for chromatic number at most 77.

References

Primary source

Jonathan C. Dahlke, “The Abu-Khzamx2013Langston Conjecture for Graphs with α(G) = 2”, arXiv:2605.28159 (2026).

Additional references

4 papers in this index state this conjecture (2015–2026). The statement above is taken from the most recent of them; the others are arXiv:2510.05893, arXiv:1512.00513, arXiv:1502.01786.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.