0
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • 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
    Commented Apr 30, 2019 at 8:37
  • $\begingroup$ @BenBarber where do you find confusion in my argument? Could you please specify? $\endgroup$
    – vidyarthi
    Commented Apr 30, 2019 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
    Commented Apr 30, 2019 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
    Commented Apr 30, 2019 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
    Commented Apr 30, 2019 at 16:00

0

Reset to default

You must log in to answer this question.