The independence-number bound for clique immersions

From papers

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

Kn/α(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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.