# Thread: colouring vertices in graph theory

1. ## colouring vertices in graph theory

Compare the upper bound for the chromatic number given by Brooks' theorem with the correct value for
i) the Petersen Graph
ii) the k-cube Qk

i) upper bound = 3, chromatic number = 3
ii) upper bound = k, chromatic number = 2.

but I don't know how to explain why?

2. First a general remark. Not everybody studied Brooks' theorem and related concepts in college, but most people in this subforum know about graphs and coloring. If it is reasonable to think that the cost of learning about the concepts from your particular problem is not too high, and if you think you can benefit from the "common mathematical knowledge" of many smart(er than me) people on this forum, then it may be worth giving the definitions of the concepts involved and maybe giving some standard online reference. Of course, if it seems that "common knowledge" is not sufficient and one has to be an expert in those particular concepts, then it probably does not make sense to explain a lot, waiting for replies from people who know what you are talking about.

The upper bound given by the Brooks' theorem is the maximum vertex degree. It's relatively easy to see from the definitions that in Peterson's graph every vertex has degree 3, and in $Q_k$ every vertex has degree $k$. The 3-coloring of Peterson's graph is shown in Wikipedia. To prove that it is not 2-colorable, try to come up with a 2-coloring making only steps that are necessary (i.e., do not involve guessing the color of some vertex), and you will see that this is impossible.

The graph $Q_k$ is bipartite as described in Wikipedia, and it's also relatively easy to see why. Therefore, its chromatic number is 2.

Is it possible that I misunderstood your question and that you were asking not why the numbers are what they are, but why the upper bound is tight for Peterson's graph and not tight for $Q_k$?

3. well, no it isn't clear to me why, that's why I posted in the forum. So I could get a clearer understanding beyond wikipedia.

4. I am not sure I can say something beyond Wikipedia, even in this particular area. But did the post above answer your questions? If not, could you say which part you don't understand and why?

5. ## hello

I've got it now. the Petersen graph is a cubic graph, has degree 3. We can see that the outer 5-cycle in the Petersen graph cannot by coloured with just 2 colours, thus the chromatic polynomial is 3.

I'm slowly getting it

6. That's right. (I am not sure about the word "cubic": it does not mean that the chromatic polynomial of Petersen graph is cubic, does it?)

Concerning the cube graph Q_k, one of the definitions is that it is the set of sequences of length k where each element is 0 or 1. E.g., the 3-dimensional cube is has 8 vertices: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). If one imagines a usual 3-dimensional coordinate system with axes (x,y,z), then those 8 points would indeed form a cube.

A vertex (x,y,z) has an edge to (x',y',z') iff these two triples differ in exactly one component. For example, there is an edge between (0,1,0) and (0,1,1), but there is no edge between (0,1,0) and (0,0,1): that would be a diagonal in one of the cube's surfaces. So, each vertex (x,y,z) has exactly three neighbors obtained by changing x, y, or z (but only one of those).

It is clear that two connected vertices have the number of 1's that differ by 1: if one has 0 in k-th position, then it's neighbor has 1. Therefore, if the number of 1's in one vertex is even, then that number of any of its neighbors is odd. Thus, we can divide vertices into even and odd, so that no two even and no two odd vertices are connected. This means that the graph is bipartite, and its chromatic number is 2.