Repository logo
  • English
  • Deutsch
  • Español
  • Français
  • Log In
    New user? Click here to register.Have you forgotten your password?

  • English
  • Deutsch
  • Español
  • Français
  • Log In
    New user? Click here to register.Have you forgotten your password?
Repository logo
  • Communities & Collections
  • Research Outputs
  • Fundings & Projects
  • Researchers
  • Statistics
  1. Home
  2. Current Research Information System UV
  3. Publicaciones
  4. Clique Immersions And Independence Number
 
  • Details
Options

Clique Immersions And Independence Number

Journal
European Journal of Combinatorics
Date Issued
2022-12-01
Author(s)
Sebastián Bustamante
Quiroz, Daniel  
Facultad de Ingeniería  
Maya Stein
José Zamora
DOI
10.1016/j.ejc.2022.103550
WoS ID
WOS:000861270900001
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.
Subjects

Computational Theory ...

Discrete Mathematics ...

Geometry And Topology...

Mathematics

Theoretical Computer ...

OCDE Subjects

Natural Sciences::Phy...

Quartile (Date Issued)
Q2
License
acceso abierto

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback

Hosting & Support by

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science