Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
PDF
  • A map colour theorem for the union of graphs
    Stiebitz, Michael ; Škrekovski, Riste
    Leta 1890 je Heawood podal zgornjo mejo za kromatično število grafov vloženih na dano ploskev z Eulerjevim rodom ▫$q \ge 1$▫. Ta zgornja meja je danes znana kot Heawoodovo število ▫$H(g)$▫. Skoraj ... celo stoletje kasneje sta Ringel in Young dokazala, da je Heawoodovo število ▫$H(g)$▫ natančna zgorja meja za kromatično število in tudi za klično število grafov vloženih na ploskev z Eulerjevim rodom ▫$g \ge 1$▫, ki je različna od Kleinove steklenice. V članku je podan rezultat Heawoodovega tipa za po povezavah disjunktno unijo dveh grafov vloženih na dano ploskev ▫$\Sigma$▫. Bolj natančno: določeno je tako število ▫$H_2(\Sigma)$▫, da je ▫$$\omega(G_1) + \omega(G_2) \le \chi(G_1) + \chi(G_2) \le H_2(\Sigma)$$▫, če je graf ▫$G$▫, ki je vložen na ▫$\Sigma$▫, disjunktna unija grafov ▫$G_1$▫ in ▫$G_2$▫. Podobno kot pri rezultatu Ringela in Youngsa pokažemo še, da je ▫$H_2(\Sigma)$▫ natančna meja za vse ploskve razen za eno neorientabilno ploskev.
    Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 96, iss. 1, 2006, str. 20-37)
    Type of material - article, component part
    Publish date - 2006
    Language - english
    COBISS.SI-ID - 13849433
    DOI

Shelf entry