New estimates for the gap chromatic number

The gap chromatic number, gap(G)gap(G), is a graph colouring parameter introduced by M.A. Tahraoui, E. Duchêne, and H. Kheddouci in Tahraoui et al. (2012). From an edge labelling f:E→{1,…,k}f:E→{1,…,k} of a graph G=(V,E)G=(V,E) on nn vertices, an induced vertex colouring ll is constructed by colouring vertices of degree greater than one by the difference between their maximum and their minimum incident edge labels. Vertices of degree one get their incident edge label as colour. The gap chromatic number gap(G)gap(G) is the minimum kk, for which a labelling ff of GG exists such that ll is injective. It is conjectured in Tahraoui et al. (2012) that, for all graphs without isolated edges or vertices (connected or not), gap(G)≤n+1gap(G)≤n+1, but the only general bound proved is 2|E|−12|E|−1.We prove the conjecture for connected graphs and disprove it in general by exhibiting a class of graphs with gap colouring number n+2n+2. For graphs without isolated edges or vertices, we prove the bound gap(G)≤n+9gap(G)≤n+9.