The vertex set of a graph G can be partitioned into two disjoint subsets X and Y such that X induces a clique in G (i.e. a complete subgraph of G) and Y is an independent set. Let m = |X|. What are the possible values of the chromatic number of G in terms of m? Explain your answer.

So this is a question I have to solve for my discrete math 2 class.

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. I am not sure how to find the solution of this question.


1 Answer 1


Hints: How many colors are needed just for the vertices in $X$? What would force an additional color for a vertex in $Y$?

  • $\begingroup$ So there would be m colors needed for vertices in X. So an additional new color would be used for a vertex in y if it were colored to all the vertices in set X ? $\endgroup$
    – JMR
    Commented Feb 8, 2021 at 15:59
  • $\begingroup$ Yes, but change colored to adjacent. Now would anything force more than one additional color? $\endgroup$
    – RobPratt
    Commented Feb 8, 2021 at 16:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .