# 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? Commented Jul 8, 2010 at 16:46
• (In other words, it's no harder than ordinary graph coloring, and I would guess that it's exactly as hard.) Commented Jul 8, 2010 at 16:48
• "NP-complete" should be changed to "NP-hard".
– Emil
Commented Jul 12, 2010 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
For every tree $$T$$ with maximum degree $$d$$, the square $$T^2$$ of $$T$$ has treewidth $$d$$ and is thus $$(d+1)$$-colourable. To see that $$T^2$$ has treewidth $$d$$, at each vertex $$v$$ of $$T$$ introduce a bag consisting of the closed neighbourhood of $$v$$.