DIKUL - logo
E-resources
Peer reviewed Open access
  • On coupon colorings of graphs
    Chen, Bob; Kim, Jeong Han; Tait, Michael; Verstraete, Jacques

    Discrete Applied Mathematics, 10/2015, Volume: 193
    Journal Article

    Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of colors from k≔{1,2,…,k} to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from k. The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G, and is denoted χc(G). In this paper, we prove that every d-regular graph G has χc(G)≥(1−o(1))d/logd as d→∞, and the proportion of d-regular graphs G for which χc(G)≤(1+o(1))d/logd tends to 1 as |V(G)|→∞. An injectivek-coloring of a graph G is an assignment of colors from k to the vertices of G such that no two vertices joined by a path of length two in G have the same color. The minimum k for which such a coloring exists is called the injective coloring number of G, denoted χi(G). In this paper, we also discuss injective colorings of Hamming graphs.