### Resumen

The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph K_{t+1} as an immersion satisfies χ(G) ≤ t. If true, this conjecture would imply that every graph with n vertices and independence number α contains K_{⌈n/3.5α-c⌉} as an immersion (and if α = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of K_{t+1}-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing K_{t+1} as an immersion satisfies χ(G) ≤ 3.54t + 7. Their result implies that any graph with n vertices and independence number α contains K_{2⌈n/5⌉} as an immersion, where c < 1.98. Moreover, the same authors prove that every graph of independence number 2 contains K_{⌊n/α⌋} as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least ⌈2n/9⌉ vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least ⌈4n/27⌉ -1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.

Idioma original | Inglés |
---|---|

Páginas (desde-hasta) | 221-228 |

Número de páginas | 8 |

Publicación | Electronic Notes in Theoretical Computer Science |

Volumen | 346 |

DOI | |

Estado | Publicada - 1 ene 2019 |

Evento | 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 - Belo Horizonte, Brasil Duración: 2 jun 2019 → 7 jun 2019 |

### Áreas temáticas de ASJC Scopus

- Ciencia computacional teórica
- Informática (todo)

## Huella Profundice en los temas de investigación de 'Large Immersions in Graphs with Independence Number 3 and 4'. En conjunto forman una huella única.

## Citar esto

*Electronic Notes in Theoretical Computer Science*,

*346*, 221-228. https://doi.org/10.1016/j.entcs.2019.08.020