1
$\begingroup$

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$. enter image description here
  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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Austin Mohr Nov 16 '16 at 21:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Danny_Kim Nov 16 '16 at 18:44
  • 1
    $\begingroup$ @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? $\endgroup$ – Austin Mohr Nov 16 '16 at 20:46
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.