VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Homomorphisms of triangle-free graphs without a ▫$K_5$▫-minor
    Naserasr, Reza ; Nigussie, Yared ; Škrekovski, Riste
    In the course of extending Grötzsch's theorem, we prove that every triangle-free graph without a ▫$K_5$▫-minor is 3-colorable. It has been recently proved that every triangle-free planar graph admits ... a homomorphism to the Clebsch graph. We also extend this result to the class of triangle-free graphs without a ▫$K_5$▫-minor. This is related to some conjectures which generalize the Four-Color Theorem. While we show that our results cannot be extended directly, we conjecture that every ▫$K_6$▫-minor-free graph of girth at least 5 is 3-colorable.
    Vir: Combinatorics 2006, A Meeting in Celebration of Pavol Hell's 60th Birthday (May 1-5, 2006) : special issue (Str. 5789-5798)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15281753

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disc.2008.04.005

Vnos na polico