# Relationship Between Chromatic Number and Multipartiteness

I am studying graph theory with the textbook introduction to graph theory written by Douglas B. West. In the book, the chromatic number and partite are defined by ...

## Definition

The chromatic number of a graph $G$ is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors.

## Definition

A graph $G$ is $k$-partite if $V(G)$ can be expressed as the union of $k$ (possibly empty) independent sets, where $V(G)$ represents the set of vertices of $G$.

## Statement

In addition to these two definitions, the author introduces a statement, "A graph is $k$-partite if and only if its chromatic number is at most $k$."

## My Question

1. What does "at most" mean?
• If the chromatic number can be $4, 5, 6$ or $7$, I can accept that $k$ is $7$. Given a graph, however, the chromatic number is a fixed integer. For example, the following graph's chromatic number is at most $3$? No, I think it is exact $3$.
2. Without the phrase "at most", I agree with the necessity.
• If a graph's chromatic number is $k$, it is $k$-partite ($\because$ $V(G)$ can be expressed as the union of $k$ independent sets.)
3. However, I do not agree with the sufficiency.
• For any graph with $n$ verticies, its vertices can be expressed as the union of $n$ independent sets. (i.e., every vertices' color is different.) Then, the graph is $n$-partite. However, its chromatic number may be less than or equal to $n$. I think it may be $n$ when every vertices are adjacent pair-wisely. Thus, I think the statement that a graph is $k$-partite only if its chromatic number is at most $k$, is wrong!

What is the problem of my thoughts? I believe that the author's claim is correct. Please answer without any slang. I can understand the literary English, but cannot the spoken English. Thank you for reading my question.

• It is true to say that the chromatic number of the graph in your example is: exactly 3, at most 3, at most 100 (it's certainly not bigger than 100, being that it is exactly 3) – Austin Mohr Nov 16 '16 at 21:14

If a graph is $k$-partite, then its chromatic number is at most $k$.

Color each of the partite sets monochromatically to get a proper $k$-coloring of the graph. It could be that a different coloring would use fewer than $k$ colors, but that would only lower the chromatic number, so the chromatic number is at most $k$.

If the chromatic number of a graph is at most $k$, then it is $k$-partite.

Take a proper $k$-coloring of the graph (which exists, since the chromatic number is at most $k$). Since there are no edges within a color class, each color class is also an independent set, so the graph is $k$-partite.

• I edited a bit, adding a graph figure. The definition of the chromatic number is by itself minimum number of colors, isn't it? I agree with the statement, "If a graph is $k$-partite, then at least $k$ colors are needed to label the vertices so that adjacent vertices receive different colors." However, I cannot accept the statement the author wrote. – Danny_Kim Nov 16 '16 at 18:44
• @Danny_Kim You are correct that the chromatic number refers to the minimum number $k$ of colors such that a proper $k$ coloring exists. The following is not true: If a graph is $k$-partite, then at least $k$ colors are needed to label the vertices. If I have a bipartite graph, then it is not true to say that "maybe three colors are needed for a proper coloring". Certainly no more than two are needed. It is true, however, that three colors would suffice to provide a proper coloring, but you could get by with fewer. Am I addressing your concern at all? – Austin Mohr Nov 16 '16 at 20:46

If a connected graph has n vertices, we can split it into n different independent sets and call that graph n-partite. Of course, we can color it with less than n colors. If we assume all these statements to be true, whatever author is saying seems to be wrong.

However, when we say graph is k-partite, it means that graph can be split into k maximal independent sets and each of the set can be colored by one color. In that case, k will always be the chromatic number (minimum colors required to color the entire graph). It cannot be more than that for a graph to be k-partite.

• The author's claims are not wrong, you might want to remove that from your answer. – postmortes Aug 19 '18 at 16:05