Abstract | ||
---|---|---|
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 Kt+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α⌉ as an immersion (and if α = 2, the two statements are known to be equivalent). |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.entcs.2019.08.020 | Electronic Notes in Theoretical Computer Science |
Keywords | Field | DocType |
Graph immersion,independence number,chromatic number,Hadwiger's conjecture | Discrete mathematics,Complete graph,Graph,Independence number,Clique,Vertex (geometry),Upper and lower bounds,Computer science,Conjecture | Journal |
Volume | ISSN | Citations |
346 | 1571-0661 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sebastián Bustamante | 1 | 0 | 2.03 |
Daniel A. Quiroz | 2 | 0 | 0.68 |
maya stein | 3 | 81 | 15.65 |
José Zamora | 4 | 7 | 5.95 |