Skip to main content
3 of 3
added 225 characters in body
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Coloring a graph formed by cliques sharing at most one point

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.

vidyarthi
  • 2.1k
  • 1
  • 16
  • 22