1
$\begingroup$

Which chromatic number $\chi(G)$ (vertex coloring number) is necessary and which is sufficient for the following undirected Graph:

$G = (V, E)$ with

$V = \{1,2,3,4,5,6,7\}$ and

$E = \{\{1,2\}, \{1,6\}, \{2,3\}, \{2,4\}, \{3, 5\}, \{3,7\}, \{4,6\}, \{5,7\}, \{6,7\}\}$

I know that the Graph $G$ can be colored with at least 3 colors without conflicts, for instance:

Vertices 1, 3, 4 (red)

Vertices 2, 5, 6 (green)

Vertex 7 (blue)

So $\chi(G) = 3 $ is the necessary chromatic number or is $\chi(G) \le 3$ is necessary, since $1$ and $2$ are necessary for $3$?

A different coloring could be, that each vertex has a unique color. In this case $\chi(G) = 7$ would be the sufficient chromatic number since there are $7$ vertices. Or is $\chi(G) \le 7$ the sufficient number, since the graph could be colored also with $4, 5$ or $6$ colors?

Could anyone tell me please, what is wrong and what is right?

Thanks

$\endgroup$
  • $\begingroup$ 3 is necessary because (3,5,7) form a triangle. So there cannot be a 2 coloring (try coloring a triangle with 2 colors). 3 is also sufficient, since you have a valid coloring with 3 colors. 7 is also sufficient, but you can do better with 3. $\endgroup$ – Artimis Fowl Dec 7 '17 at 5:48
2
$\begingroup$

Part of your confusion seems to be about terminology and notation, so let me address that.

We can say "$k$ colors are necessary to (properly) color $G$": this means you cannot color $G$ with fewer than $k$ colors. For clarity, you can say "At least $k$ colors are necessary to color $G$", but this means exactly the same thing. In your particular example, we can make statements such as:

  • $1$ color is necessary, because $G$ has vertices, and they need to be given colors.
  • $2$ colors are necessary, because vertices $1$ and $2$ are adjacent, so just coloring them requires two different colors.
  • $3$ colors are necessary, because any two of the vertices $3$, $5$, and $7$ are adjacent, so coloring these three vertices requires three different colors.

(In general, there could be subtler reasons why $k$ colors are necessary, but that's all we've got in this example.)

We can say "$k$ colors are sufficient to (properly) color $G$": this means that there exists a coloring with $k$ colors. In your example, we can say:

  • $3$ colors are sufficient, because there is a coloring of $G$ with three colors: color vertices $1,3,4$ red, vertices $2,5,6$ green, and vertex $7$ blue.
  • $4$ colors are sufficient, because the above coloring is also a coloring of $G$ with the four colors red, green, blue and yellow. It happens never to use yellow.
  • The same argument shows why larger number of colors are sufficient, too.
  • Another reason why $7$ colors are sufficient is that we can give every vertex its own color. (In general, for an $n$-vertex graph, $n$ colors are always sufficient.)

But there is no such thing as the "necessary chromatic number" or "sufficient chromatic number" of a graph. The chromatic number $\chi(G)$ of a graph $G$ always refers to the least number of colors we can use to color $G$, so in this example $\chi(G)=3$. It's always exactly one number (even when we don't know it yet, and even if we're thinking about suboptimal colorings that use a different number of colors). To prove that $\chi(G)=3$, we need to show that $3$ colors are sufficient (there is a $3$-coloring of $G$) and that $3$ colors are necessary (we can't color $G$ with fewer colors).

The statement "$k$ colors are necessary to color $G$" is equivalent to saying that $\chi(G) \ge k$, and the statement "$k$ colors are sufficient to color $G$" is equivalent to saying that $\chi(G) \le k$. But that's just a way of putting a sentence into mathematical notation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.