[Math] Understanding connection between independent set and chromatic number

coloringgraph theory

I have came across following facts / definitions:

  1. Maximum independent set: Independent set of largest possible size.
  2. Maximal independent set: Independent set such that adding any other vertex to the set forces the set to contain an edge
  3. Independence number: Number of vertices in the maximum independent set
  4. Relation between chromatic number ($χ$) and independence number ($β$)
    We can color vertices in maximum independent set themselves in single color and they will form largest number of vertices with same color. Hence, largest number of vertices with same color cannot exceed the independence number. Hence, $β≥\frac{n}{χ}$.
  5. Relation with chromatic number: Chromatic number = size of minimum maximal independent set
  6. Chromatic partitioning involves partitioning all vertices of graph into the smallest possible number of "disjoint" independent sets.

My doubts:

D1. Is fact 5 simply wrong?
D2. Is that "disjoint" in fact 6 should really be "minimal"?
D3. Is every maximum independent set always maximal?

Best Answer

D1 : this is wrong. For example the complete bipartite &K_{5,5}& has two maximal independent set, each one of size 5. The chromatic number is 2, not 5. I think it should be something close to $n$ divided by the minimal maximal independent set size (to check), using something close to your previous definition.

D2 : it's a matter of definition : usually it has to be minimal as you want the chromatic partitioning to have the chromatic number of sets in the partition. You could define it otherwise, then even the partition made of sets, each one with a single vertice would be valid.

D3 : no. Consider the complete bipartite graph $K_{5,3}$. The maximum independent set has size 5, but the other set of 3 vertices is also maximal (you cannot add a vertice and keep it independent)

edit 1 sorry I read your question 3) a bit fast. Yes, every maximum independent set has to be maximal, otherwise you could add a vertices, keeping it independent, and you'd get a bigger independent set, a contradiction with the maximum definition. But the other direction is not true. Some maximal independent sets are not maximum (as per my original answer)

Related Question