Colourings of Graphs with extra conditions

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)

• Isn't this equivalent to coloring the graph G' which has the same vertices as G and edges wherever two of the corresponding vertices in G are either one or two edges apart? – Qiaochu Yuan Jul 8 '10 at 16:46
• (In other words, it's no harder than ordinary graph coloring, and I would guess that it's exactly as hard.) – Qiaochu Yuan Jul 8 '10 at 16:48
• "NP-complete" should be changed to "NP-hard". – Emil Jul 12 '10 at 22:35

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