Clique immersions and independence number
| dc.contributor.author | Bustamante, Sebastián | |
| dc.contributor.author | Quiroz, Daniel A. | |
| dc.contributor.author | Stein, Maya | |
| dc.contributor.author | Zamora, José | |
| dc.date.accessioned | 2023-04-11T21:58:44Z | |
| dc.date.available | 2023-04-11T21:58:44Z | |
| dc.date.issued | 2022-12 | |
| dc.description | Indexación: Scopus. | es |
| dc.description.abstract | The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains Kχ(G) as an immersion. If true, this would imply that every graph with n vertices and independence number α contains K⌈[Formula presented]⌉ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph G contains an immersion of a clique on ⌈[Formula presented]⌉ vertices. Their result implies that every n-vertex graph with independence number α contains an immersion of a clique on ⌈[Formula presented]−1.13⌉ vertices. We improve on this result for all α≥3, by showing that every n-vertex graph with independence number α≥3 contains an immersion of a clique on ⌊[Formula presented]⌋−1 vertices, where f is a nonnegative function. © 2022 | es |
| dc.description.uri | https://www-sciencedirect-com.recursosbiblioteca.unab.cl/science/article/pii/S0195669822000464?via%3Dihub | |
| dc.identifier.citation | European Journal of CombinatoricsOpen AccessVolume 106December 2022 Article number 103550 | es |
| dc.identifier.doi | 10.1016/j.ejc.2022.103550 | |
| dc.identifier.issn | 0195-6698 | |
| dc.identifier.uri | https://repositorio.unab.cl/xmlui/handle/ria/48451 | |
| dc.language.iso | en | es |
| dc.publisher | Academic Press | es |
| dc.rights.license | Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0) | |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es | |
| dc.subject | Hadwiger's Conjecture | es |
| dc.subject | Connected Graph | es |
| dc.subject | Graph | es |
| dc.title | Clique immersions and independence number | es |
| dc.type | Artículo | es |
Archivos
Bloque original
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- Bustamante_Clique_immersions_and_independence_number.pdf
- Tamaño:
- 416.01 KB
- Formato:
- Adobe Portable Document Format
- Descripción:
- TEXTO COMPLETO EN INGLES
Bloque de licencias
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- license.txt
- Tamaño:
- 1.71 KB
- Formato:
- Item-specific license agreed upon to submission
- Descripción: