Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano
  • (1, k)‐Coloring of Graphs w...
    Choi, Hojin; Choi, Ilkyoo; Jeong, Jisu; Suh, Geewon

    Journal of graph theory, April 2017, 2017-04-00, 20170401, Letnik: 84, Številka: 4
    Journal Article

    A graph is (d1,...,dr)‐colorable if its vertex set can be partitioned into r sets V1,...,Vr so that the maximum degree of the graph induced by Vi is at most di for each i∈{1,...,r}. For a given pair (g,d1), the question of determining the minimum d2=d2(g,d1) such that planar graphs with girth at least g are (d1,d2)‐colorable has attracted much interest. The finiteness of d2(g,d1) was known for all cases except when (g,d1)=(5,1). Montassier and Ochem explicitly asked if d2(5, 1) is finite. We answer this question in the affirmative with d2(5,1)≤10; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K=K(γ) where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.