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$
1
  • $\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$ Dec 7, 2017 at 5:48

1 Answer 1

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$

You must log in to answer this question.

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