Name
Abstract | ||
|---|---|---|
Following in the spirit of the Hadwiger and Hajos conjectures, Abu-Khzam and Langston have conjectured that every k-chromatic graph contains an immersion of K-k. They proved this for k <= 4. Much before that, Lescure and Meyniel [10] obtained a stronger result that included also the values k = 5 and 6, by proving that every simple graph of minimum degree k - 1 contains an immersion of K-k. They noted that they also have a proof of the same result for k = 7 but have not published it due to the length of the proof. We give a simple proof of this result. This, in particular, proves the conjecture of Abu-Khzam and Langston for every k <= 7. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.26493/1855-3974.112.b74 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Immersion,Hadwiger Conjecture | Graph theory,Hadwiger conjecture (graph theory),Graph,Combinatorics,Chromatic scale,Dirac (video compression format),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 2 | 1855-3966 |
Citations | PageRank | References |
9 | 0.65 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| matt devoss | 1 | 9 | 0.65 |
| Ken-ichi Kawarabayashi | 2 | 1731 | 149.16 |
| Bojan Mohar | 3 | 1523 | 192.05 |
| haruko okamura | 4 | 9 | 0.65 |