A note on neighbour-distinguishing regular graphs total-weighting

Jakub Przybyło

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

We investigate the following modification of a problem posed by Karoński, Łuczak and Thomason [J. Combin. Theory, Ser. B 91 (2004) 151–157]. Let us assign positive integers to the edges and vertices of a simple graph $G$. As a result we obtain a vertex-colouring of $G$ by sums of weights assigned to the vertex and its adjacent edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary $G$? We know that the answer is yes if $G$ is a 3-colourable, complete or 4-regular graph. Moreover, it is enough to use weights from $1$ to $11$, as well as from $1$ to $\lfloor{\chi(G)\over2}\rfloor+1$, for an arbitrary graph $G$. Here we show that weights from $1$ to $7$ are enough for all regular graphs.

Détail

DOI : 10.37236/910

Classification : 05C78, 05C15
Mots-clés : vertex colouring, proper colouring, regular graphs