As a phd-student I've wandered into a question of colourings of graphs and wondered what was known about them.


Given a finite graph G, where the maximum degree of a vertex is d, I'm interested in colourings where not only are no adjacent vertices the same colour, but also that no vertex has two neighbours of the same colour. [in other words, a vertex and all vertices adjacent to it, are all coloured distinctly] 


It's easy to see that the number of colours is at least d + 1, and I'm interested in when this is this actual number of colours needed. (although information on the general case is also of interest)


Also within my work I am mainly looking at regular graphs. But again, that is merely the cases I'm working with and information, thoughts, references on the general case would be muchly appreciated. 


To pose it as specific questions:


When can a graph G be coloured, as above, with only d + 1 colours? 


When can a regular graph G be coloured, as above, with only d + 1 colours? 


Is it NP-Complete to find such colourings? (I feel it is because it seems similar to edge colourings)



Colourings of Graphs with extra conditions
Qiaochu Yuan commented that your problem is equivalent to coloring what is known as the **square** $G^{2}$ of the graph $G$. For more details on coloring the square of a graph, see "The chromatic number of graph powers", N. Alon and B. Mohar, Combinatorics, Probability and Computing (1993) 11, 1-10. On-line at <http://www.math.tau.ac.il/~nogaa/PDFS/am8.pdf> 


