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 ...
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.
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$.
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$."
- What does "at most" mean?
- 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.