Latest update

# necessary and sufficient chromatic number $\chi$ of a graph

2017-12-10 03:52:33

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

• 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 y

2017-12-10 05:31:08