UNI-MB - logo
UMNIK - logo
 
(UL)
  • Immersing small complete graphs
    DeVos, Matt ...
    Following in the spirit of the Hadwiger and Hajós conjectures, Abu-Khzam and Langston have conjectured that every ▫$k$▫-chromatic graph contains an immersion of ▫$K_k$▫. They proved this for ▫$k \le ... 4$▫. Much before that, Lescure and Meyniel [F. Lescure and H. Meyniel, On a problem upon configurations contained in graphs with given chromatic number, Graph theory in memory of G.A. Dirac (Sandbjerg, 1985), 325-331, Ann. Discrete Math. 41, North-Holland, Amsterdam, 1989] 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 \le 7$▫.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 3, no. 2, 2010, str. 139-146)
    Vrsta gradiva - članek, sestavni del
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15856473

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/viewFile/112/109
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 3, no. 2, 2010, str. 139-146)

loading ...
loading ...
loading ...

Vnos na polico