2
$\begingroup$

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)

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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? $\endgroup$
    – Qiaochu Yuan
    Commented Jul 8, 2010 at 16:46
  • 1
    $\begingroup$ (In other words, it's no harder than ordinary graph coloring, and I would guess that it's exactly as hard.) $\endgroup$
    – Qiaochu Yuan
    Commented Jul 8, 2010 at 16:48
  • $\begingroup$ "NP-complete" should be changed to "NP-hard". $\endgroup$
    – Emil
    Commented Jul 12, 2010 at 22:35

3 Answers 3

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

As mentioned already, the concept you are studying is know as colouring the square G2. Such a colouring is also known as a distance-2-colouring of a graph. You can find extensive literature using one of these search terms.

Deciding if G2 can be coloured with k colours for a given input graph G is NP-complete, even if G has to come from very special classes of graphs. For instance, the main result in "M. Mahdian, On the computational complexity of strong edge coloring. Discrete Appl. Math. 118 (2002), 239--248" is equivalent to the statement: for fixed k and g, deciding if G2 can be k-coloured for a bipartite graph G with girth (=length of shortest cycle) at least g is NP-complete.

Regarding your question about graphs G with maximum degree D that can be distance-2-coloured with D+1 colours, I don't think much is known about that. One class of graphs for which this is known are outerplanar graphs with large enough maximum degree. See: "K.-W. Lih and W.-F. Wang, Coloring the square of an outerplanar graph. Taiwanese J. Math. 10 (2006), 1015--1023". Of course, outerplanar graphs are hardly ever regular (they always have vertices of degree at most two).

I'm not aware of results on the question: "given a (regular) graph G with maximum degree D, can its square be coloured with D+1 colours?" I would expect it's NP-hard as well.

Improve this answer
$\endgroup$
0
$\begingroup$

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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .