It is true that very graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set

Let G is a graph such that $C_1, C_2, ......, C_\theta$ are the set of maximal cliques which cover every vertex in G. Suppose if every clique cover $C_i$ is contained in some maximum clique of size $\omega$ then is it true that graph G contains a minimum vertex-coloring such that at least one color class is a maximum independent set?

  • $\begingroup$ A graph is not a thing that can contain a color class. A coloring of a graph is something that has a color class. In your first sentence and in your last sentence, then, you should specify: do you mean that every coloring of a graph has this property, or that some coloring of a graph has this propertty? (Or maybe some other option, such as every coloring with the minimum number of colors...) $\endgroup$ – Misha Lavrov Apr 15 at 13:43
  • $\begingroup$ @Misha: I have edited the statement. I hope it is correct now. $\endgroup$ – James Alex Apr 15 at 13:49

Your Answer

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

Browse other questions tagged or ask your own question.