E-viri
Recenzirano
-
Choi, Ilkyoo; Esperet, Louis
Journal of graph theory, 20/May , Letnik: 91, Številka: 1Journal Article
A graph G is (d1,…,dk)‐colorable if its vertex set can be partitioned into k sets V1,…,Vk, such that for each i∈{1,…,k}, the subgraph of G induced by Vi has maximum degree at most di. The Four Color Theorem states that every planar graph is (0,0,0,0)‐colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is (2,2,2)‐colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus g>0 is (0,0,0,9g−4)‐colorable and (2,2,9g−4)‐colorable. Moreover, these graphs are also (0,0,O(g),O(g))‐colorable and (2,O(g),O(g))‐colorable. We also prove that every triangle‐free graph that is embeddable on a surface of Euler genus g is (0,0,O(g))‐colorable. This is an extension of Grötzsch's Theorem, which states that triangle‐free planar graphs are (0,0,0)‐colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus g is (0,O(g))‐colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on g are tight up to a constant multiplicative factor.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.