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
- 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$.
- 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$.
- 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.)
- 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.
Best Answer
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.