\([1, 1, 2]\)-Colorings of \(K_5\) and \(K_6\)

Abstract

Given non-negative integers \(r, s\), and \(t\), an \([r, s, t]\)-coloring of a graph \(G = (V(G), E(G))\) is a mapping \(c\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k-1\}\) such that \(|c(v_i) – c(v_j)| \geq r\) for every two adjacent vertices \(v_i, v_j\), \(|c(e_i) – c(e_j)| \geq s\) for every two adjacent edges \(e_i, e_j\), and \(|c(v_i) – c(e_i)| \geq t\) for all pairs of incident vertices and edges, respectively. The \([r, s, t]\)-chromatic number \(\chi_{r,s,t}(G)\) of \(G\) is defined to be the minimum \(k\) such that \(G\) admits an \([r, s, t]\)-coloring. We prove that \(\chi_{1,1,2}(K_5) = 7\) and \(\chi_{1,1,2}(K_6) = 8\).