Consider a graph formed by $k$ $k$ order cliques sharing at most one point. Consider thedegenerate case of all cliques disjoint, which is trivially $k$ colorable. Now, to colour any other such graph, we first color any one clique.

Now, if any vertex of the colored clique is shared by $m$ cliques, then, we could put at maximum $k-(m-1)$ vertices to expand the color class containing that vertex, which are chosen one from each clique not sharing that vertex. Such a vertex exists, by construction(as otherwise, other cliques would be sharing that vertex) . This corresponds to the number of reduced vertices from $k^2$ vertices, which is the degenerate case of all cliques being disjoint. Proceeding so on for all vertices of the colored clique, I think we can cover all the vertices of the graph by expanding the color classes to the required deficiency. Thus, the graph as a whole would be $k-$ colorable.

Is the above assertion right? Or are there any counterexamples? Any light on this. Thanks beforehand.

  • 3
    $\begingroup$ This is a famous open problem. en.wikipedia.org/wiki/… I'm afraid I don't quite follow what you're suggesting well enough to pinpoint a mistake. $\endgroup$ – Ben Barber Apr 30 '19 at 8:37
  • $\begingroup$ @BenBarber where do you find confusion in my argument? Could you please specify? $\endgroup$ – vidyarthi Apr 30 '19 at 10:36
  • $\begingroup$ Your argument doesn't address the fact that the other cliques (except for the initial one) can intersect. That causes a problem in the "proceeding so on" stage. $\endgroup$ – Michal Adamaszek Apr 30 '19 at 11:55
  • 1
    $\begingroup$ So note that what I wrote just above has a problem (for one, in general, the vertex you choose in the $k-(m-1)$ cliques cannot be arbitrary, as those cliques might intersect). But again, I am just asking if I understood correctly. Apologies if I didn’t. $\endgroup$ – EGME Apr 30 '19 at 14:37
  • 1
    $\begingroup$ I will try to read further and deeper into the rest of your argument. But, if the choice is not random, then you must specify how to choose that vertex, and then you have to prove that you can make such choices all the way to the end. I don’t see quite how to do this, or how you do it. I would be glad to hear further. If it is of any consolation, this problem has been looked at by the truly “great” graph theorists of our time, without full success. $\endgroup$ – EGME Apr 30 '19 at 16:00

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.