Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • Planar graphs of odd-girth at least 9 are homomorphic to Petersen graph
    Dvořák, Zdeněk ; Škrekovski, Riste ; Valla, Tomáš
    Let ▫$G$▫ be a graph and let ▫$c : V (G) \to {\{1,...,5\}\choose 2}$▫ be an assignment of 2-element subsets of the set ▫$\{1,...,5\}$▫ to the vertices of ▫$G$▫ such that for every edge ▫$vw$▫, the ... sets ▫$c(v)$▫ and ▫$c(w)$▫ are disjoint. We call such an assignment a (5,2)-coloring. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph. The odd-girth of a graph ▫$G$▫ is the length of the shortest odd cycle in ▫$G$▫ (▫$\infty$▫ if ▫$G$▫ is bipartite). We prove that every planar graph of odd-girth at least 9 is (5,2)-colorable, and thus it is homomorphic to the Petersen graph. Also, this implies that such graphs have fractional chromatic number at most ▫$\frac{5}{2}$▫ As a special case, this result holds for planar graphs of girth at least 8.
    Vrsta gradiva - knjiga ; neleposlovje za odrasle
    Založništvo in izdelava - Ljubljana : Institute of Mathematics, Physics and Mechanics, Department of Mathematics, 2001
    Jezik - angleški
    COBISS.SI-ID - 35449347

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/01001.pdf

Dostopna je elektronska verzija dokumenta ali pa gre za elektronski vir
loading ...
loading ...
loading ...

Vnos na polico