The independence-number bound for clique immersions

About 7 years old · traced to

Let GG be an nn-vertex graph, and let α(G)\alpha(G) denote its independence number. Independence-number clique immersion conjecture. The graph GG contains

K⌈n/α(G)⌉K_{\lceil n/\alpha(G)\rceil}

as an immersion.

This conjecture extends Vergara's conjecture from independence number 22 to arbitrary independence number. The bound is motivated by the inequality χ(G)≥⌈n/α(G)⌉\chi(G)\ge \lceil n/\alpha(G)\rceil and would follow from the immersion analogue of Hadwiger's conjecture; current results provide weaker lower bounds.

References

Primary source

Sebastián Bustamante, Daniel A. Quiroz, Maya Stein and José Zamora, “Clique immersions and independence number”, arXiv:1907.01720 (2022).

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.